单调栈

发表于2024-07-25更新于2024-07-26

单调栈

何时用单调栈

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

那么单调栈的原理是什么呢？为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢？

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。

单调栈怎们用

  • 栈中元素存什么
    存元素下标

  • 单调栈里元素是递增呢？ 还是递减呢？

    • 首先是递增和递减的判断是指，从栈口到栈底
    • 递增：求左边或者右边第一个比他大的元素
    • 递减：求左边或者右边第一个比他晓得元素

  • 单调栈的作用
    存放遍历过的元素

  • 主要判断条件
    当前遍历元素T[i]与T[st.pop()]的关系

    • 1、T[i] > T[st.pop()] i-st.pop() i进栈
    • 2、T[i] == T[st.pop()] i-st.pop() i进栈
    • 3、T[i] < T[st.pop()] i进栈

图 8

题目

每日温度

图 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var dailyTemperatures = function(temperatures) {
  let n = temperatures.length
  let stack = [0]
  let res = Array(n).fill(0)
  for(let i=1;i<n;i++){
    let top = stack[stack.length-1]
    //小于和等于的情况，直接压入栈
    if (temperatures[i] === temperatures[top]){
      stack.push(i)
    }
    else if(temperatures[i] < temperatures[top]){
      stack.push(i)
    }
    //当前元素大于栈顶元素的情况，要计算距离，
    //删掉栈顶元素知道所有小于当前元素的栈顶元素被删完，压入当前元素
    else{
      while (stack.length && temperatures[i] > temperatures[stack[stack.length-1]]) {
        top = stack.pop()
        res[top] = i-top
      }
      stack.push(i)
    }
  }
  return res
};

下一个更大元素 I

图 9

思路
用到hash,将nums1存在map中，键位nums1中的元素，值为nums1中元素的索引

使用单调栈解决问题，遍历数组nums2，根据条件进行不同处理

  • 1、当前元素小于或等于栈顶元素，当前元素压入栈
  • 2、当前元素大于栈顶元素，查看栈顶元素是否出现在nums1中，如果在，那么及已经找到的他右边的较大元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var nextGreaterElement = function (nums1, nums2) {
  const m = nums1.length
  const n = nums2.length
  let stack = [nums2[0]]
  let res = Array(m).fill(-1)
  let map = new Map()
  for (let i = 0; i < m; i++) {
    map.set(nums1[i],i)
  }
  for (let j = 1; j < n; j++) {
    let top = stack[stack.length-1]
    if (nums2[j]<top || nums2===top) stack.push(nums2[j])
    else{
        // console.log(res)
        while(stack.length && nums2[j]>stack[stack.length-1]){
          top = stack.pop()
          if (map.has(top)){
            res[map.get(top)] = nums2[j]

          }
        }
        stack.push(nums2[j])
      }
  }
  return res
}

下一个更大元素

图 10

思路
数组循环了，思路是把数组复制一份拼接在原数组后面，但是这占用了空间，所以思路是遍历两次数组就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var nextGreaterElements = function(nums) {
  let n = nums.length
  let res = Array(n).fill(-1)
  let stack = [0]
  for(let i=1;i<n*2;i++){
    let j = i
    if (i>=n)  j = i - n
    while (stack.length && nums[j] > nums[stack[stack.length - 1]]) {
      let top = stack.pop()
      res[top] = nums[j]
    }
    stack.push(j)
  }
  return res
};

接雨水

图 11

图 12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var trap = function(height) {
  let n = height.length
  let res = 0
  let stack = [0]
  for(let i=1;i<n;i++){
    while(stack.length && height[i]>height[stack[stack.length-1]]){
        let top = stack.pop()
        if (stack.length === 0) break
        let topl = stack[stack.length-1]
        res += (Math.min(height[i],height[topl])-height[top]) * (i-topl-1)
    }
    stack.push(i)
  }
  return res
};

柱状图中最大的矩形

图 13

图 14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var largestRectangleArea = function(heights) {
  heights = [0,...heights,0]
  let n = heights.length
  let maxArea = 0
  let stack =[0]
  for (let i=1;i<n;i++){
    while(heights[i]<heights[stack[stack.length-1]]){
      let top = stack.pop()
      let topl = stack[stack.length-1]
      let w = i-topl-1
      maxArea = Math.max(maxArea,w*heights[top])
    }
    stack.push(i)
  }
  return maxArea
};