代码随想录_单调栈

代码随想录_单调栈

739.每日温度

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

思路: 单调栈.

• T[i] < T[st.top()]
  • 当前元素小于栈顶元素, 即从左往右遍历, T[i] < T[st.top()], 不合收集要求, 放入栈中
• T[i] = T[st.top()]
  • 当前元素等于栈顶元素, 即从左往右遍历, T[i] = T[st.top()], 不合收集要求, 放入栈中
• T[i] > T[st.top()]
  • 当前元素大于栈顶元素, 即从左往右遍历, T[i] > T[st.top()], 符合收集要求, T[i]一直与栈顶元素比较, 只要>, 就收集到res, 并弹出已比较过的下标, 直到 T[i] <= T[st.top()], 将i放入栈中

代码:

class Solution {public int[] dailyTemperatures(int[] temperatures) {// 1. 初始化, 建立单调栈int len = temperatures.length;int[] res = new int[len];// res[i]: 对i右侧第一个大于tem[i]的数值tem[j], j-iDeque<Integer> stack = new LinkedList<>();// 单调栈: 递减, 找到第一个大于栈顶的stack.push(0);// 栈中默认要放入第一个元素// 2. 根据栈填充resfor(int i = 1;i < len;i++) {// 2.1 当前值 <= 栈顶对应元素if(temperatures[i] <= temperatures[stack.peek()]) {stack.push(i);// 当前值的下标放入stack}else {// 2.2 当前值 > 栈顶对应元素// 在栈非空的情况下进行统计, while循环至temperatures[i] <= temperatures[stack.peek()], 故第二个判断不能省略while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {res[stack.peek()] = i - stack.peek();// 收集下标stack.pop();// 弹出当前栈顶较小的数值下标}stack.push(i);// 当前判断的下标放入stack, 保持从左往右 栈 单调递增}}// 3. 返回return res;}
}

496.下一个更大元素 I

496. 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• nums1和nums2中所有整数 互不相同
• nums1 中的所有整数同样出现在 nums2 中

**思路: ** 单调栈.

要建立nums1对应的map, 方便将nums2中的数据映射到等值nums1的index, 从而统计res[index] = nums2[i], 只需要在map中含有nums2[i]时才需要向res中收集.

代码:

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 1. 初始化int[] res = new int[nums1.length];Arrays.fill(res, -1);Deque<Integer> stack = new LinkedList<>();stack.push(0);// 2. 建立nums1的映射Map<Integer, Integer> map = new HashMap<>();for(int i = 0;i < nums1.length;i++) map.put(nums1[i], i);// 3. 查找比较填充for(int i = 1;i < nums2.length;i++) {if(nums2[i] <= nums2[stack.peek()]) {stack.push(i);}else {while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {// 能找到更大元素的都要popif(map.containsKey(nums2[stack.peek()])) {// 只有nums1含有的元素需要统计int index = map.get(nums2[stack.peek()]);// 找到栈顶元素(nums2中的值)对应nums1中的下标res[index] = nums2[i];// 将当前元素(下一个更大元素) 放入 res栈顶元素下标对应的位置}stack.pop();// 弹出栈顶元素}stack.push(i);// 放入当前元素}}// 4. 返回return res;}
}

503.下一个更大元素 II

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

思路: 逻辑扩充原数组

代码:

class Solution {public int[] nextGreaterElements(int[] nums) {// 1. 创建res数组int len = nums.length;int[] res = new int[len];Arrays.fill(res, -1);// 2. 创建并初始化单调栈Deque<Integer> stack = new LinkedList<>();stack.push(0);// 3. 遍历nums, 填充resfor (int i = 1; i < len * 2; i++) {// 使用%进行逻辑扩充if (nums[i % len] <= nums[stack.peek()]) {stack.push(i % len);} else {while (!stack.isEmpty() && nums[i % len] > nums[stack.peek()]) {res[stack.peek()] = nums[i % len];stack.pop();}stack.push(i % len);}}return res;}
}

42.接雨水

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

**思路: ** 单调栈, 横向计算, 相加

代码:

class Solution {public int trap(int[] height) {// 0. 特殊判断if (height.length <= 2) return 0;// 1. 单调栈逻辑Stack<Integer> stack = new Stack<>();stack.push(0);int sum = 0;// 统计总面积for (int i = 1; i < height.length; i++) {if (height[i] < height[stack.peek()]) {// 小: 加入stack.push(i);} else if (height[i] == height[stack.peek()]) {// 相同: 先弹出, 再加入stack.pop();stack.push(i);} else {// 大: 开始计算面积int right = i;// 当前遍历到的大的那个位置就是rightwhile (!stack.isEmpty() && height[i] > height[stack.peek()]) {int mid = stack.pop();// 栈离第一个小的就是midif (!stack.isEmpty()) {// 如果栈中还有元素(含left), 开始计算int left = stack.peek();// 看一眼left, 不弹, 以便下次循环判断int h = Math.min(height[left], height[right]) - height[mid];int w = right - left - 1;int s = h * w;sum += s;}}stack.push(i);// 没有更小的了, 当前元素下标加入栈中}}// 2. 返回return sum;}
}

84.柱状图中最大的矩形

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

**思路: ** 类似接雨水, 变为单调递增栈, 每找到一个更小值就可以计算面积. 但注意此处要在收尾各加一个0, 以便在计算值不足时依旧能够继续计算.

代码:

class Solution {public int largestRectangleArea(int[] heights) {// 1. 扩充原数组, 首尾加上0, 以便栈内元素不足三个的时候依旧能计算剩下的矩形面积// (接雨水不需要, 因为此时就接不了了(会流出))int[] nHeights = new int[heights.length + 2];nHeights[0] = 0;nHeights[nHeights.length - 1] = 0;for(int i = 0;i < heights.length;i++) nHeights[i + 1] = heights[i];heights = nHeights;// 2. 建立单调栈Stack<Integer> stack = new Stack<>();stack.push(0);// 3. 遍历每一个柱子, 计算并更新sint s = 0;for(int i = 1;i < heights.length;i++) {if(heights[i] > heights[stack.peek()]) {// 当前更大: 直接放stack.push(i);}else if(heights[i] == heights[stack.peek()]) {// 当前相等: 先弹再放(直接放)stack.pop();stack.push(i);}else {// // 当前更小: 遇到边界, 开始计算int rIndex = i;// 当前为右边界while(!stack.isEmpty() && heights[i] < heights[stack.peek()]) {// 开始找mIndex, lIndexint mIndex = stack.pop();// 当前栈顶为mIndexint lIndex = stack.peek();// 栈顶之后为lIndexint h = heights[mIndex];int w = rIndex - lIndex - 1;s = Math.max(s, w * h);// 取最大值}stack.push(i);// 没有比当前更小的了, 放入当前元素}}// 4. 返回return s;}
}