代码随想录算法训练营第xx天

今日任务

● 739.每日温度 ● 496.下一个更大元素I ● 503.下一个更大元素II

● 42. 接雨水 ● 84.柱状图中最大的矩形 ●

单调栈

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

在使用单调栈的时候首先要明确如下几点：

单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
单调栈里元素是递增呢？还是递减呢？

注意以下讲解中，顺序的描述为从栈顶到栈底的顺序，

739.每日温度我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

即：如果求一个元素右边第一个更大元素，单调栈就是递增的（栈顶最小），如果求一个元素右边第一个更小元素，单调栈就是递减的（栈顶最大）。

739.每日温度

链接：https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE (opens in a new tab)

题解想法

使用单调栈，栈中存储的是温度的下标，遍历数组，如果当前温度大于栈顶温度，那么就出栈，直到栈为空或者当前温度小于栈顶温度，然后将当前温度的下标入栈。

注：以下代码不用Stack<Integer> stack = new Stack<>(); 而使用Deque<Integer> stack=new LinkedList<>(); 是因为他们有性能差异。

LinkedList和Stack在栈操作（如push, pop, peek）上的性能都是常数时间复杂度（O(1)）。然而，LinkedList的实现基于链表，而Stack的实现基于向量（Vector），这意味着Stack在扩容时可能需要复制所有的元素到新的存储空间，这会带来额外的性能开销。另一方面， LinkedList在添加或删除元素时只需要改变一些指针，因此不需要这种扩容操作。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack=new LinkedList<>();
        int[] resu = new int[temperatures.length];
        stack.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            while (!stack.isEmpty()) {
                if (temperatures[i] > temperatures[stack.peek()]) {
                    resu[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                else break;
            }
            stack.push(i);
        }
        return resu;
    }
}

496.下一个更大元素I

自己想法

核心逻辑沿用上题思路，先遍历nums2，找到每个元素右边第一个更大的元素，然后遍历nums1，找到nums1中元素在nums2中的位置，然后找到对应的结果。

为了提高效率，使用hashmap存储nums2中元素的位置。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack=new LinkedList<>();
        int[] resu2 = new int[nums2.length];
        int[] resu1 = new int[nums1.length];
        Map<Integer, Integer> map = new HashMap<>(nums2.length);
        stack.push(0);
        Arrays.fill(resu2, -1);
        map.put(nums2[0], 0);
        for (int i = 1; i < nums2.length; i++) {
            map.put(nums2[i], i);
            while (!stack.isEmpty()) {
                if (nums2[i] > nums2[stack.peek()]) {
                    resu2[stack.peek()] = nums2[i];
                    stack.pop();
                }
                else break;
            }
            stack.push(i);
        }
        for (int i = 0; i < nums1.length; i++) {
            resu1[i] = resu2[map.get(nums1[i])];
        }
        return resu1;
    }
}

503.下一个更大元素II

自己想法

和上题思路一样，只是这里是循环数组，所以遍历两次数组。我这里直接将数组复制一份出来。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] twin_nums = new int[nums.length * 2];
        for (int i = 0; i < nums.length; i++) {
            twin_nums[i] = nums[i];
            twin_nums[i + nums.length] = nums[i];
        }
        Deque<Integer> stack=new LinkedList<>();
        int[] resu = new int[nums.length];
        Arrays.fill(resu, -1);
        stack.push(0);
        for (int i = 1; i < twin_nums.length; i++) {
            while (!stack.isEmpty()) {
                if (twin_nums[i] > twin_nums[stack.peek()]) {
                    resu[stack.peek() % nums.length] = twin_nums[i];
                    stack.pop();
                }
                else break;
            }
            stack.push(i);
        }
        return resu;
    }
}

当然也可以不复制数组，直接使用取余数的方式。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack=new LinkedList<>();
        int[] resu = new int[nums.length];
        Arrays.fill(resu, -1);
        stack.push(0);
        for (int i = 1; i < nums.length * 2; i++) {
            int tmp_i = i % nums.length;
            while (!stack.isEmpty()) {
                if (nums[tmp_i] > nums[stack.peek()]) {
                    resu[stack.peek()] = nums[tmp_i];
                    stack.pop();
                }
                else break;
            }
            stack.push(tmp_i);
        }
        return resu;
    }
}

42. 接雨水

题解想法1-按列接雨水

算双指针解法吧。

总共遍历3次，

第一次遍历，找到截至每个元素左边的最大值；

第二次遍历，找到截至每个元素右边的最大值；

第三次遍历，找到每个元素左右最大值的最小值，减去当前元素的值。

注意第一个和最后一个元素不可能接雨水，所以不用考虑。

class Solution {
    public int trap(int[] height) {
        if (height.length <= 2) return 0;
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        leftMax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }
        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }
        int ans = 0;
        for (int i = 1; i < height.length - 1; i++) {
            ans += Math.max(0, (Math.min(leftMax[i], rightMax[i]) - height[i]));
        }
        return ans;
    }
}

题解想法2-按行接雨水

单调栈解法。

https://programmercarl.com/0042.%E6%8E%A5%E9%9B%A8%E6%B0%B4.html#%E5%8D%95%E8%B0%83%E6%A0%88%E8%A7%A3%E6%B3%95 (opens in a new tab)

84.柱状图中最大的矩形

自己想法

按列考虑，最大矩形一定可以由当前柱子的高度向左右扩展得到。

如果最终答案不是由当前柱子的高度决定的，那么一定可以找到一个柱子，使得它的高度比当前柱子的高度小，且扩展的宽度比当前柱子的宽度大。

那么最大矩形就不是由当前柱子得到，而是由那个柱子得到。

但是对于那个柱子而言，遍历到自己时，那个柱子就是“当前柱子”

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 寻找每个元素右边第一个小于自己的元素下标
        Deque<Integer> stackR = new LinkedList<>();
        int[] resuR = new int[heights.length];
        Arrays.fill(resuR, -1);
        stackR.push(0);
        for (int i = 1; i < heights.length; i++) {
            while (!stackR.isEmpty()) {
                if (heights[i] < heights[stackR.peek()]) {
                    resuR[stackR.peek()] = i;
                    stackR.pop();
                }
                else break;
            }
            stackR.push(i);
        }
        // 寻找每个元素左边第一个小于自己的元素下标
        Deque<Integer> stackL = new LinkedList<>();
        int[] resuL = new int[heights.length];
        Arrays.fill(resuL, -1);
        stackL.push(heights.length - 1);
        for (int i = heights.length - 2; i >= 0 ; i--) {
            while (!stackL.isEmpty()) {
                if (heights[i] < heights[stackL.peek()]) {
                    resuL[stackL.peek()] = i;
                    stackL.pop();
                }
                else break;
            }
            stackL.push(i);
        }
        // 找最大
        int ans = 0;
        for (int i = 0; i < heights.length; i++) {
            int left = -1;
            int right = heights.length;
            if (resuL[i] != -1) left = resuL[i];
            if (resuR[i] != -1) right = resuR[i];
            int tmp = (right - left - 1) * heights[i];
            if (tmp > ans) ans = tmp;
        }
        return ans;
    }
}