单调栈算法

题目概述

单调栈：栈，并且栈是有序的
单调栈的两种写法：
左 -> 右，或者右 -> 左 建议使用左到右的写法

及时去掉无用元素，保证栈中元素有序

从左到右的思路中，更新是在while循环中的，也就是说while 是满足题目条件，用于解放栈中的元素的

基础题目

739.每日温度
1475.商品折扣后的最终价格

矩形

84.柱状图中最大的矩形

题目详解

739.每日温度

思路分析：这个题目如果使用暴力，则时间复杂度为o(n^2)，会超时，我们可以考虑使用单调栈
单调栈：使用栈进行存储，并且栈内的元素是单调的
为什么使用单调栈？：假设我们从左往右进行计算，则我们需要寻找当前的temperature[i]的后续的第一个大的温度，如果找不到的话，我们首先得存储起来这个数，然后向后面遍历，如果后续 遇到了比最后一个存储起来的元素大的数，我们就解决了这个数，直到没有满足，按照这个顺序存储的数组，是单调的，并且都是先进后出，所以我们使用单调栈

# 从左到右的写法
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # 先用暴力求解，但是会超时，是o(n^2)
        # 考虑使用单调栈，先进后出，并且栈是有序的
        ans = [0]*(len(temperatures))
        st = []
        for i,c in enumerate(temperatures):
            # 如果栈不为空并且当前的元素比栈顶的元素大
            while st and c > temperatures[st[-1]]:
                # 栈顶的元素找到了temperature[i]，则弹出
                ans[st[-1]] = i - st[-1]
                st.pop()
            st.append(i)
        return ans

# 从右到左的写法，替换上面的for循环即可
        for i in range(len(temperatures)-1,-1,-1):
            tem = temperatures[i]
            while st and tem >= temperatures[st[-1]]:
                st.pop()
            if st:
                ans[i] = st[-1] - i
            st.append(i)

1475.商品折扣后的最终价格

这题也比价简单，只用套模版即可

# 从左到右思路
class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        # 使用单调栈进行求解，单调栈存储的是 没有找到满足情况的元素的下标
        ans = [i for i in prices]
        st = []
        for i,c in enumerate(prices):
            # while 是解放栈的,只要当前元素小于等于栈顶即可
            while st and c <= prices[st[-1]]:
                ans[st[-1]] -= c 
                st.pop()
            st.append(i)
        return ans

84.柱状图中最大的矩形

思路分析：这个题目与基础的单调栈不同，需要考虑栈中剩余的元素，以及矩形的宽度，从一开始的情况

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        ans = [0]*(len(heights))  # 初始化 ans 为全零数组
        st = []
        
        for i in range(n):
            # 当前的数 heights[i] 小于栈顶就可以解放栈里面元素
            while st and heights[i] < heights[st[-1]]:
                top = st.pop()
                # 计算以 heights[top] 为高的矩形的面积
                width = i if not st else i - st[-1] - 1
                ans[top] = heights[top] * width
            st.append(i)
        
        # 处理栈中剩余的元素
        while st:
            top = st.pop()
            width = n if not st else n - st[-1] - 1
            ans[top] = heights[top] * width
        
        return max(ans)