第一篇 单调栈

单调栈介绍

单调栈是一种理解起来很容易,但是运用起来并不那么简单的数据结构。一句话解释单调栈,就是一个栈,里面的元素的大小按照他们所在栈内的位置,满足一定的单调性。那么到底什么时候用这个单调栈,怎么用单调栈呢。我们先来看几个例子,然后总结一下模板。

经典入门题

Description

❓ 给一个数组,返回一个大小相同的数组。返回的数组的第i个位置的值应当是,对于原数组中的第i个元素,至少往右走多少步,才能原到一个比自己大的元素(如果之后没有比自己大的元素,或者已经是最后一个元素,则在返回数组的对应位置放上-1)。

Example 1:

Input: 5, 3, 1, 2, 4
Output: -1, 3, 1, 1, -1

💡 对于数组中的每个数字,要找到第一个比他大的数字,如果直接暴力来做,则对于一个单调递减的数组,比如[7, 6, 5, 4, 3, 2 ,1] ,每次都要走到数组的末尾,其时间复杂度为O(n2)。而用单调栈可以使时间复杂度达到O(n)。

代码如下:

public int nextExceed(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            res[stack.peek()] = i - stack.pop();
        }
        stack.push(i);
    }
    return res;
}

我们通过维护一个严格单调递减的栈,从而计算结果。

一般来讲,在尝试单调栈的方法之前,应该先判断是维护单调递增还是单调递减的栈。当然,在本题中是严格单调递减的栈,具体是否严格应根据题意来定。

触类旁通

84. Largest Rectangle in Histogram

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Deque<Integer> stack = new ArrayDeque<>();
    int res = 0;

    for (int i = 0; i <= n; i++) {
        int h = i == n ? 0 : heights[i];
        while (!stack.isEmpty() && h <= heights[stack.peek()]) {
            int curH = heights[stack.pop()];
            int right = i;
            int left = stack.isEmpty() ? -1 : stack.peek();
            res = Math.max(res, curH*(right - left - 1));
        }
        stack.push(i);
    }
    return res;
}

💡 本题中,我们维护一个不严格单调递增的栈。并在heights数组的末尾添加了一个0。

img

以[2, 1, 5, 6, 2, 3]为例:

当i=3时,heights[i]=6, 此时的stack为[1, 2, 3]。

当i=4时,heights[i]=2,此时满足进入while循环的条件。此时curH=6,右边界right=i=4,左边界left=2,因此计算的就是第4个矩形的面积,6*(4 – 2 – 1) = 6。计算出res后满足第二次while循环条件,此时curH=5,有边界right=4,左边界left=1,因此计算的就是图中的虚线部分面积。

最后当i=5时,stack为[1, 5],为了让stack中的结果都得到计算,因此我们在heights数组最后额外加一个高度为0的空矩形。从而保证所有的可能都被计算。对于额外增加空矩形的代码,我们可以直接创建一个n+1的大小的newHeights数组,但是其实可以用更为简便且不需要额外内存的方式,即遍历n。

int h = i == n ? 0 : heights[i];

Follow up

❓ 每个矩形的宽不一定等于1,此时最大的面积又是多大呢?

💡 代码如下:

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Deque<Integer> stack = new ArrayDeque<>();
    int res = 0;

    for (int i = 0; i <= n; i++) {
        int h = i == n ? 0 : heights[i];
        while (!stack.isEmpty() && h <= heights[stack.peek()]) {
            int curH = heights[stack.pop()];
            int right = i;
            int left = stack.isEmpty() ? -1 : stack.peek();
            int width = 0;
            for (int j = left + 1; j < right; j++) {
                width += nums[j][0];
            }
            res = Math.max(res, h*width);
        }
        stack.push(i);
    }
    return res;
}

739. Daily Temperatures

public int[] dailyTemperatures(int[] temperatures) {
    Deque<Integer> stack = new ArrayDeque<>();
    int[] ret = new int[temperatures.length];
    for(int i = 0; i < temperatures.length; i++) {
        while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            ret[idx] = i - idx;
        }
        stack.push(i);
    }
    return ret;
}

💡 和经典例题几乎一样,维护一个严格单调递减的栈。

503. Next Greater Element II

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    if (n == 0) return new int[0];
    int[] newNums = new int[2*n - 1];
    for (int i = 0; i < n - 1; i++) {
        newNums[i] = nums[i];
        newNums[i + n] = nums[i];
    }
    newNums[n - 1] = nums[n - 1];
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < 2*n - 1; i++) {
        while (!stack.isEmpty() && newNums[i] > newNums[stack.peek()]) {
            int idx = stack.pop();
            res[idx] = newNums[i];
        }
        if (i < n) {
            stack.push(i);
        }
    }
    return res;
}

💡 这里我们化圈为直,将大小为n的环形数组转换成大小为2*n - 1的数组。这个思想在前面分析区间dp中的环形石子归并题目中也有用到。

42. Trapping Rain Water

public int trap(int[] height) {
    int n = height.length;
    if (n <= 1) return 0;

    int start = 0;
    while (start < n && height[start] == 0)
        start++;

    int res = 0;
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int low = height[stack.pop()];
            if (!stack.isEmpty()) {
                res += (Math.min(height[stack.peek()], height[i]) - low) * (i - stack.peek() - 1);
            }
        }
        stack.push(i);
    }
    return res;
}

💡 这道题稍微绕一点,是个hard难度的题。我们仍然需要先思考到底维护递增栈还是递减栈。很显然,如果我们维护一个递减栈,当我们遇到一个较大的数时,就可以盛水了。

962. Maximum Width Ramp

public int maxWidthRamp(int[] A) {
    int n = A.length;
    if (n == 0) return 0;
    Deque<Integer> stack = new ArrayDeque<>();
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (stack.isEmpty() || A[i] < A[stack.peek()]) 
            stack.push(i);
    }
    for (int i = n - 1; i > res; i--) {
        while (!stack.isEmpty() && A[i] >= A[stack.peek()])
            res = Math.max(res, i - stack.pop());
    }
    return res;
}

💡 这道题又绕了一下,一般我们认为单调栈是找下一个更大或者更小的元素。然而这道题是解决最后一个更大或者更小的问题。解决思路是先顺序按照单调栈计算一遍,随后逆序遍历一遍。

239. Sliding Window Maximum

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> stack = new ArrayDeque<>();

    int l = 0;
    for (int r = 0; r < n; r++) {
        // remove numbers out of range k
        while (!stack.isEmpty() && stack.peek() < r - k + 1)
            stack.poll();
        // remove smaller numbers in k range as they are useless
        while (!stack.isEmpty() && nums[stack.peekLast()] < nums[r])
            stack.pollLast();
        stack.offer(r);
        if (r >= k - 1) {
            res[l++] = nums[stack.peek()]; 
        }
    }
    return res;
}

💡 这道题其实也不算单调栈,而更像是单调队列。具体逻辑看代码就行了

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号