力扣爆刷第82天--单调栈一网打尽

力扣爆刷第82天–单调栈一网打尽

文章目录

• • • 力扣爆刷第82天--单调栈一网打尽
    • 一、739. 每日温度
    • 二、496.下一个更大元素 I
    • 三、503.下一个更大元素II
    • 四、42. 接雨水
    • 五、84.���状图中最大的矩形

      一、739. 每日温度

      题目链接：https://leetcode.cn/problems/daily-temperatures/

      （）

      思路：求距离当前元素最近的比其大或者比其小的元素，这种是非常典型的单调栈场景。求第一个温度大于当前天的距离，这种就用单调栈，栈顶元素小于遍历元素就出栈，然后记录下距离，这个距离就是距离栈顶元素第一个大于的温度的距离。

      class Solution {   public int[] dailyTemperatures(int[] temperatures) {        Deque stack = new LinkedList();        int[] nums = new int[temperatures.length];        for(int i = 0; i  
      二、496.下一个更大元素 I
       
      题目链接：https://leetcode.cn/problems/next-greater-element-i/
      （）
      思路：求nums1在nums2中相等元素位置的右侧最近第一大元素，关键在于nums1与nums2的映射关系，可以在单调栈遍历之前设置map记录关系，也可以在单调栈遍历的过程中记录关系并且在后面访问map形成结果。
       
      class Solution {    public int[] nextGreaterElement(int[] nums1, int[] nums2){       Map map = new HashMap();       for(int i = 0; i  
      三、503.下一个更大元素II
       
      题目链接：https://leetcode.cn/problems/next-greater-element-ii/
      思路：和第一题类似，不过要求nums是循环数组，但凡是循环数组都可以把数组长度虚拟成两倍，然后遍历即可解决。这是一个小技巧，剩下的就是单调栈的使用了。
       
      class Solution {  public int[] nextGreaterElements(int[] nums) {       Deque stack = new LinkedList();       int len = nums.length;       int[] res = new int[len];       Arrays.fill(res, -1);       for(int i = 0; i  
      四、42. 接雨水
       
      题目链接：https://leetcode.cn/problems/trapping-rain-water/
      思路：利用单调栈栈内单调的特性结合大于栈顶的元素构造出凹槽，即 stack栈顶下第一个元素，stack栈顶，大于栈顶的元素，3者构成一个可以接雨水的凹槽。
       
      class Solution {   public int trap(int[] height) {        int sum = 0, len = height.length;        Deque stack = new LinkedList();        for(int i = 0; i  
      五、84.柱状图中最大的矩形
       
      题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
      思路：本题刚好和上一题相反，本题需构造凸型，当元素小于栈顶时出栈，即可使得 stack顶下一个元素，stack元素，当前元素，构成凸型，初始状态只计算栈顶这一列，当有元素再出栈时，宽度就会随i - stack.peek() - 1;而变宽。
      int mid = stack.pop();
      int h = heights[mid];
      int w = i - stack.peek() - 1;
       
      class Solution {   public int largestRectangleArea(int[] heights) {       int[] newHeights = new int[heights.length+2];        for (int i = 0; i  heights[i]) {                int mid = stack.pop();                int h = heights[mid];                int w = i - stack.peek() - 1;                max = Math.max(max, h * w);            }            stack.push(i);        }        return max;    }}