目录

 

167. 两数之和 II - 输入有序数组

88. 合并两个有序数组

26. 删除排序数组中的重复项

76. 最小覆盖子串

32. 最长有效括号

155. 最小栈

84. 柱状图中最大的矩形

42. 接雨水

239. 滑动窗口最大值

918. 环形子数组的最大和

167. 两数之和 II - 输入有序数组

思路：

一般双指针的主要思路是先找到暴力解法，然后考虑有没有单调性之类的性质可以利用，再进行优化
	
使用i,j两个指针，初始位置在0和数组末尾，若相加的结果大于target则说明当前的结果需要减小，则j往前移；若相加的结果小于target则说明当前的结果需要增大，则i往后移。
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        i, j = 0, n-1
        while i<j:
            if numbers[i] + numbers[j] < target:
                i += 1
            elif numbers[i] + numbers[j] > target:
                j -= 1
            else:
                return [i+1, j+1]

88. 合并两个有序数组

思路：

这道题就是基本的归并思想
	
由于题目要求的是把结果存入nums1中，则要注意不能从前开始比较合并，要从后面开始
	
这里需要注意的是如果p1,p2赋初值为m-1，n-1，可能就取不到下标为0的那个数
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # nums1的最大数指针 nums2的最大数指针 结果集的最大数指针
        p1, p2, p3 = m, n, m+n
        while p1 and p2:
            if nums1[p1-1] >= nums2[p2-1]:
                nums1[p3-1] = nums1[p1-1]
                p1 -= 1
            else:
                nums1[p3-1] = nums2[p2-1]
                p2 -= 1
            p3 -= 1
        while p2:
            nums1[p3-1] = nums2[p2-1]
            p2 -= 1
            p3 -= 1

26. 删除排序数组中的重复项

思路：

由于不能申请额外空间，考虑直接在数组上进行操作。
	
设置两个指针，一个指向当前需要存储数的位置k，一个对数组进行扫描i
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                nums[k] = nums[i]
                k += 1
        return k

76. 最小覆盖子串

思路：

首先一样的步骤，考虑暴力解法，会需要O（n^2）的时间复杂度
	
然后考虑单调性，我们可以使用两个指针，i，j指示答案字符串的首尾。当i逐渐往后移，j必定只能往后增加，不可能往前，因为那样会包含了最佳答案在里面，不可能得到最短的。
	
这样的话，维护一个hash表，记录t字符串每个字符出现的次数，最后考虑的就是i依次往后遍历，j从起点开始，i往后一格，将hash对应位置-1，j也往后，若当前所指的位置hash表中对应结果小于0了，说明这个字符不在答案中，j往后移
	
再维护一个答案t所需要几个不同的字符，当都得到了，比较一下当前s[j:i+1]的长度，用res记录最短的即是答案
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        hash_table = {}
        for ch in t:
            hash_table[ch] = hash_table.get(ch, 0) + 1
        cnt = len(hash_table.items())

        res = ""
        c, j = 0, 0
        for i in range(len(s)):
            num = hash_table.get(s[i], 0)
            if num == 1:
                c += 1
            elif num==0:
                hash_table[s[i]] = hash_table.get(s[i], 0)
            hash_table[s[i]] -= 1
            # j从前往后
            while hash_table[s[j]] < 0 and j<i:
                hash_table[s[j]] += 1
                j += 1
            if c==cnt:
                if not res or len(res)>i-j+1:
                    res = s[j:i+1]
        return res

32. 最长有效括号

思路：

首先需要记住括号序列的一个重要性质：假如将（当做数字1，）当做数字-1；则合法的括号序列前缀和一定是>=0的，并且整个序列的最终结果肯定是0
	
start枚举当前这一段的开头，cnt记录前缀和。
	
若是当前的cnt<0了，说明这一段是不合法的，start=i+1，cnt=0
	
若是当前的cnt>0，继续做
	
若是当前的cnt==0，说明当前的这一段是合法的，比较和res的长度，若大于则更新res
	
注意，为了防止出现((())这种情况，也就是最后的和不会等于0的情况，所以还需要反过来再做一遍
	
（和）的ascii码二进制相差一位，可以直接异或处理
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        reverse_s = list(s[::-1])
        for index, ch in enumerate(reverse_s):
            reverse_s[index] = chr(ord(ch)^1)
        return max(self.work(s), self.work("".join(reverse_s)))
    
    def work(self, s):
        """
        返回当前子串的最长长度
        """
        start, cnt = 0, 0
        n = len(s)
        res = 0
        for i in range(n):
            if s[i] == "(":
                cnt += 1
            else:
                cnt -= 1
                if cnt < 0:
                    start = i+1
                    cnt = 0
                elif cnt == 0:
                    res = max(res, i-start+1)
        return res

155. 最小栈

思路：

这个题有点类似于前缀和，始终要维护一个前缀和的最小数。
	
用两个栈，一个是模拟栈操作的，一个是始终保存当前栈中最小的数字
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.stack_min = []


    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.stack_min:
            self.stack_min.append(x)
        else:
            self.stack_min.append(min(self.stack_min[-1], x))

    def pop(self) -> None:
        self.stack.pop()
        self.stack_min.pop()


    def top(self) -> int:
        return self.stack[-1]


    def getMin(self) -> int:
        return self.stack_min[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

tips:单调栈（查找每个数左侧第一个比它小的数）；单调队列=滑动窗口内的最值
84. 柱状图中最大的矩形

思路：

如何枚举所有的情况？枚举所有柱形的上边界，作为整个矩形的上边界
	
然后找出左右边界，找出左边离它最近，比它小且最高的矩形；找出右边离它最近，比它小且最高的矩形。
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left, right = [0]*n, [0]*n
        stk = []
        for i in range(n):
            while stk and heights[stk[-1]]>=heights[i]:
                stk.pop()
            if not stk:
                left[i] = -1
            else:
                left[i] = stk[-1]
            stk.append(i)
        while stk:
            stk.pop()
        for i in range(n-1, -1, -1):
            while stk and heights[stk[-1]]>=heights[i]:
                stk.pop()
            if not stk:
                right[i] = n
            else:
                right[i] = stk[-1]
            stk.append(i)
        res = 0
        for i in range(n):
            res = max(res, heights[i]*(right[i]-left[i]-1))
        return res

42. 接雨水

思路：

这道题用栈保存当前最小的高度，当出现一个比栈顶高的高度，则弹出进行这一小部分的计算。
	
整体接雨水的方式就是一小块一小块加起来
class Solution:
    def trap(self, height: List[int]) -> int:
        stk = []
        res = 0
        for i in range(len(height)):
            last = 0
            while stk and height[stk[-1]] <= height[i]:
                t = stk.pop()
                res += (i-t-1) * (height[t]-last)
                last = height[t]
            if stk:
                res += (i-stk[-1]-1)*(height[i]-last)
            stk.append(i)
        return res

239. 滑动窗口最大值

思路：

滑动窗口的最大值主要思路就是保持一个队列，队列中始终保持一个递减的队列。
	
队头始终是当前窗口最大值，队尾始终是当前窗口最小值。
	
当队头超过了窗口范围弹出即可。
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q, res = [], []
        for i in range(len(nums)):
            if q and i-k>=q[0]:
                q.pop(0)
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
            if i-k+1>=0:
                res.append(nums[q[0]])
        return res

918. 环形子数组的最大和

思路：

这类环形数组题，可以考虑的tips是将其展开为一排，展开为2n的一排，这样就变成了控制一个长度为n的滑动窗口，求窗口内的最大值
	
求前缀和，sum_[i]-sum_[j]就是j+1...i的和，用res记录最大值，时刻更新即可
class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        n = len(A)
        for i in range(n):
            A.append(A[i])
        sum_ = [0]*(2*n)
        for i in range(2*n):
            sum_[i] = sum_[i-1] + A[i]
        queue = [0]
        res = sum_[0]
        for i in range(1, 2*n):
            if queue and i - n>queue[0]:
                queue.pop(0)
            if queue:
                res = max(res, sum_[i] - sum_[queue[0]])
            while queue and sum_[i] <= sum_[queue[-1]]:
                queue.pop()
            queue.append(i)
        return res


 

 

1. 单调队列（双端队列）

       核心思想是维持deque/双端队列中的元素保持递增or递减。

       使用该数据结构的优点是deque在队列两端都可以添加、删除元素，这里借助了它其中4种常数时间复杂度的操作(java)：offerLast(n)、getFirst()、pollFirst()、pollLast()。



单调栈介绍详见：https://blog.csdn.net/LutherK/article/details/107023543

另外：单调队列还被应用于“多重背包问题”的优化解法。

 

2. 例题

Leetcode 239题目：

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7] 

解释: 

 

  滑动窗口的位置                最大值

---------------               -----

[1  3  -1] -3  5  3  6  7       3

 1 [3  -1  -3] 5  3  6  7       3

 1  3 [-1  -3  5] 3  6  7       5

 1  3  -1 [-3  5  3] 6  7       5

 1  3  -1  -3 [5  3  6] 7       6

 1  3  -1  -3  5 [3  6  7]      7

 

3. 图解

思路：

      在一堆数字中，已知最值，如果给这堆数添加一个数，那么比较一下就可以很快算出最值；但如果减少一个数，就不一定能很快得到最值了，而要遍历所有数重新找最值。

      首先考虑，要在O(N)的时间内解决此问题，我们需要3个O(1)的操作帮助我们完成，分别是：

              push(n)：在队列末尾添加元素n；

              max：取当前队列/窗口中的最大值；

              pop(n)：r若队首元素是n，则删除n；

     在Java中的实现如下：

​
    // 用于"单调队列"的成员内部类
    private static class MonotonicQueue {
        Deque<Integer> deque = new ArrayDeque<>();
        void push(int n){
            while(!deque.isEmpty() && deque.getLast()<n)
                deque.pollLast();
            deque.offerLast(n);
        }
        //
        int max(){
            return deque.getFirst();
        }
        //
        void pop(int n){
            if(!deque.isEmpty() && deque.getFirst()==n)
                deque.pollFirst();
        }
    }

​



 

4. 完整Java代码

    // (2) 双端队列（单调队列）
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        MonotonicQueue window = new MonotonicQueue();
        int[] res = new int[n-k+1];
        for(int i=0;i<n;i++){
            if(i<k-1)
                window.push(nums[i]);
            else {
                window.push(nums[i]);
                res[i-k+1] = window.max();
                window.pop(nums[i-k+1]);
            }
        }
        return res;
    }

    // 用于"单调队列"的成员内部类
    private static class MonotonicQueue {
        Deque<Integer> deque = new ArrayDeque<>();
        void push(int n){
            while(!deque.isEmpty() && deque.getLast()<n)
                deque.pollLast();
            deque.offerLast(n);
        }
        //
        int max(){
            return deque.getFirst();
        }
        //
        void pop(int n){
            if(!deque.isEmpty() && deque.getFirst()==n)
                deque.pollFirst();
        }
    }

补充：

此题还有另外一种解法，时间复杂度也是O(N)，可以说是DP，也可是看做“同步双向遍历”。

代码：

    // （1）动态规划
    // left[i] 表示从窗口开始到下标i的最大值
    // right[j]  表示从窗口末尾到索引j的最大值
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        if (k == 1) return nums;

        int[] left = new int[n];
        left[0] = nums[0];
        int[] right = new int[n];
        for (int i = 1; i < n; i++) {
            if (i%k==0) left[i] = nums[i];
            else
                left[i] = Math.max(left[i-1],nums[i]);
            int j = n-1-i;
            if((j+1)%k==0)
                right[j] = nums[j];
            else
                right[j] = Math.max(right[j+1],nums[j]);
        }
        int[] res = new int[n-k+1];
        for (int i = 0; i <= n - k; i++) {
            res[i] = Math.max(right[i],left[i+k-1]);
        }
        return res;
    }

纯属个人见解，如有错误望批评指正！

 

 

Topic:

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

Example 1:
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：

滑动窗口的位置                最大值

[1  3  -1] -3  5  3  6  7       3

1 [3  -1  -3] 5  3  6  7       3

1  3 [-1  -3  5] 3  6  7       5

1  3  -1 [-3  5  3] 6  7       5

1  3  -1  -3 [5  3  6] 7       6

1  3  -1  -3  5 [3  6  7]      7

Example 2:
输入：nums = [1], k = 1

输出：[1]
Example 3:
输入：nums = [1,-1], k = 1

输出：[1,-1]
Example 4:
输入：nums = [9,11], k = 2

输出：[11]
Example 5:
输入：nums = [4,-2], k = 2

输出：[4]
Solution：
一开始的思路其实是将每个窗口的值遍历在栈中

同时每次max栈中的值返回在ans中

但是由于max函数运行效率太低，无法通过运算量过大的样例

所以利用滑动窗口法对思路进行简化避免使用max函数：
首先对nums一一遍历，并维持一个单调递减栈

先将第一个值的索引入栈

若后面遍历的值比栈中索引对应的最小的值要小则直接索引入栈

只要后面遍历的值比栈中索引对应的值要大或相等则将最后一个值去除

直到后面遍历的值比栈中索引对应的的值要小则将对应的索引入栈

以此重复维持一个单调递减栈
但是由于k（滑动窗口）的长度是一定的

则利用滑动窗口的方法

若最大值的索引小于窗口的左边界（i - k）则将最左侧的值去除

而i就是实时右边界所以无需处理右边界
同时当窗口存在（i + 1 >  k时）：

每一次遍历（移动窗口）将栈中最大值的索引对应的最大值加入ans中
Code：
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        a = collections.deque()
        ans = []

        for i in range(len(nums)):
            while a and nums[a[-1]] <= nums[i]:
                a.pop()
            
            a.append(i)
        
            if a[0] <= i - k:
                a.popleft()
            if i + 1 >= k:
                ans.append(nums[a[0]])
        
        return ans


Result：

文章目录
1. 题目信息
2. 解题
2.1 暴力法
2.2 双端队列法

1. 题目信息
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
进阶：
你能在线性时间复杂度内解决此题吗？
来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sliding-window-maximum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 暴力法
双重循环查找，O（nk）复杂度


class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() == 0)
            return {};
        int maxnum, i, j;
        vector<int> ans;
        for(i = 0; i < nums.size()-k+1; ++i)
        {
            maxnum = nums[i];
            for(j = i+1; j < k+i; ++j)
            {
                if(nums[j] > maxnum)
                    maxnum = nums[j];
            }
            ans.push_back(maxnum);
        }
        return ans;
    }
};

2.2 双端队列法
将双端队列看做栈，单调递减栈法。

在双端队列里保存下标
队首保存最大的，队尾保存小的
但是注意规则：


过了窗口的范围的删除
在窗口范围内的k个，每加入一个数nums[i]，只保留前面比它大的，<=nums[i] 的没必要存在，该窗口内它是比较大的

对 {1,3,-1,-3,5,3,6,7}，k = 3

先建立前k个元素的队列：{1}，{1，3}，{1，3，-1}（队列变化过程）（为了方便我用元素值表示）

对后面n-k个元素分别操作：

{3，-1，-3}

{-1，-3， 5}

{-3， 5，3}

{5，3，，6}

{3，6，7}

每次取出队首就是答案。3，3，5，5，6，7

每个元素进出队列，时间复杂度O(n)


class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() == 0)
            return {};
        deque<int> q;
        vector<int> ans;
        int i;
        for(i = 0; i < k; ++i)
        {
            while(!q.empty() && nums[i] >= nums[q.back()])
            {
                q.pop_back();// <=nums[i]的前面的存的，无意义，删掉
            }
            q.push_back(i);
        }
        ans.push_back(nums[q.front()]);
        for(i = k; i < nums.size(); ++i)
        {
            if(!q.empty() && i-k+1 > q.front())
                q.pop_front();//过了窗口了，删除
            while(!q.empty() && nums[i] >= nums[q.back()])
            {
                q.pop_back();
            }
            q.push_back(i);
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

《剑指Offer》面试题59 - I. 滑动窗口的最大值
class Solution {	//2020.2.21
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty())
            return {};
        int l = 1, r = 0;
        vector<int> ans;
        deque<int> q;
        while(k--)
        {
            while(!q.empty() && nums[q.back()] <= nums[r])
            {
                q.pop_back();
            }
            q.push_back(r++);
        }
        ans.push_back(nums[q.front()]);
        while(r < nums.size())
        {
            if(q.front() < l)
                q.pop_front();
            while(!q.empty() && nums[q.back()] <= nums[r])
            {
                q.pop_back();
            }
            q.push_back(r++);
            l++;
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};