正文
题目分析：一开始，看到题目，没有任何的想法，但是深入的了解一下，发现，其实，在我们计算的时候，可以按照每一个位置向后探索可以到达的最远位置，那么就是我们本题的答案。但是，如何保存我们探索的记忆呢？一个是使用队列，或者单调栈或者双指针进行互相的配合。
本题是使用的双指针：
时间复杂度O(N)
空间复杂度O(1)
class Solution { /** * 采用双指针来进行实现 * * @param s 第一个字符串 * @param t 第二个字符串 * @param maxCost 最高的花费 * @return 返回最长的字串 */ public int equalSubstring(String s, String t, int maxCost) { // 设置双指针 左位置 右位置 返回值 以及 总体的花费 int left = 0, right = 0, res = 0, totalCost = 0; // 计算字符串的长度 int n = s.length(); // 循环求解 for (; right < n; right++) { // 计算当前的花费 int cost = Math.abs(s.charAt(right) - t.charAt(right)); // 计算总花费 totalCost += cost; // 判断是否超过预期 if (totalCost > maxCost) { // 超过预期最大值的处理 while (totalCost > maxCost) { int costA = Math.abs(s.charAt(left) - t.charAt(left)); totalCost -= costA; left++; } // 计算最大的字串 res = Math.max(res, right - left + 1); } else { // 计算 res = Math.max(res, right - left + 1); } } // because right is the next location res = Math.max(res, right - left); return res; } }
