当前位置：首页 > news >正文

代码随想录day45：单调栈篇

news 来源：原创 2024/5/16 13:08:11

文章目录

- day45：单调栈篇
- - 739.每日温度
  - 496.下一个更大元素 I
  - 503.下一个更大元素 II
  - 42.接雨水
  - 84.柱状图中最大的矩形

day45：单调栈篇

739.每日温度

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

496.下一个更大元素 I

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Stack<Integer> stack = new Stack<>();int[] ans = new int[nums1.length];Arrays.fill(ans, -1);Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++)map.put(nums1[i], i);stack.push(0);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()]) {if (map.containsKey(nums2[stack.peek()])) {ans[map.get(nums2[stack.peek()])] = nums2[i];}stack.pop();}stack.push(i);}}return ans;}
}

503.下一个更大元素 II

class Solution {public int[] nextGreaterElements(int[] nums) {int n = nums.length;int[] ans = new int[n];Arrays.fill(ans, -1);Stack<Integer> stack = new Stack<>();for (int i = 0; i < 2 * n; i++) {while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {ans[stack.pop()] = nums[i % n];}stack.push(i % n);}return ans;}
}

42.接雨水

class Solution {public int trap(int[] height) {Stack<Integer> stack = new Stack<>();int sum = 0;for (int i = 0; i < height.length; i++) {while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int h_pop = height[stack.pop()];if (stack.isEmpty()) break;int h = Math.min(height[stack.peek()], height[i]) - h_pop;int w = i - stack.peek() - 1;sum += h * w;}stack.push(i);}return sum;}
}

84.柱状图中最大的矩形

class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> stack = new Stack<>();int[] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int i = 0; i < heights.length; i++)newHeights[i + 1] = heights[i];heights = newHeights;int ans = 0;stack.push(0);for (int i = 1; i < heights.length; i++) {while (heights[i] < heights[stack.peek()]) {int mid = stack.pop();int left = stack.peek();int w = i - left - 1;int h = heights[mid];ans = Math.max(ans, h * w);}stack.push(i);}return ans;}
}