数据结构与算法-单调栈

2022-11-06 HGNULB 约 32 分钟

文章信息 1 个分类 · 1 个标签

分类

数据结构与算法

标签

单调栈

一、相邻最值

496. 下一个更大元素 I

先为 nums2 中每个值寻找右侧第一个更大值，再回答 nums1 的查询。栈保存尚未找到答案的值，当前值更大时弹栈并写入映射；nums2 没有重复值，可以直接用值作为键，没有答案时返回 -1。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int num : nums2) {
            // 当前值弹出所有比它小的栈顶，栈顶的答案就是当前值
            while (!stack.isEmpty() && num > stack.peek()) {
                nextGreater.put(stack.pop(), num);
            }

            stack.push(num);
        }

        int[] res = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
            res[i] = nextGreater.getOrDefault(nums1[i], -1);
        }

        return res;
    }
}

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    nextGreater := make(map[int]int)
    var stack []int

    for _, num := range nums2 {
        // 当前值弹出所有比它小的栈顶，栈顶的答案就是当前值
        for len(stack) > 0 && num > stack[len(stack)-1] {
            nextGreater[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, num)
    }

    res := make([]int, len(nums1))
    for i, num := range nums1 {
        if v, ok := nextGreater[num]; ok {
            res[i] = v
        } else {
            res[i] = -1
        }
    }
    return res
}

503. 下一个更大元素 II

用下标取模模拟两轮遍历，为数组尾部寻找环绕后的答案。栈保存待结算下标，当前值严格更大时弹栈；只在第一轮入栈，第二轮只结算。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];

        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];

            while (!stack.isEmpty() && num > nums[stack.peek()]) {
                res[stack.pop()] = num;
            }

            // 只在第一轮入栈，第二轮只结算
            if (i < n) {
                stack.push(i);
            }
        }

        return res;
    }
}

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }

    var stack []int
    for i := 0; i < 2*n; i++ {
        num := nums[i%n]
        for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
            res[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        // 只在第一轮入栈，第二轮只结算
        if i < n {
            stack = append(stack, i)
        }
    }
    return res
}

739. 每日温度

栈保存还未遇到更高温度的日期下标，对应温度从栈底到栈顶非递增。当前温度严格更高时弹出下标，等待天数就是当前下标减去被弹出的下标；相等温度不能结算。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int pre = stack.pop();

                // 弹出时结算等待天数
                res[pre] = i - pre;
            }

            stack.push(i);
        }

        return res;
    }
}

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    res := make([]int, n)
    var stack []int

    for i := 0; i < n; i++ {
        for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
            pre := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            // 弹出时结算等待天数
            res[pre] = i - pre
        }
        stack = append(stack, i)
    }
    return res
}

1019. 链表中的下一个更大节点

先将链表节点值转成数组，再用单调栈保存尚未找到答案的下标。遇到严格更大值时弹栈并填写答案，没有更大值的位置保持 0。

class Solution {
    // 栈中保存还没有找到下一个更大值的节点下标，且对应值保持单调递减。
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> values = new ArrayList<>();

        while (head != null) {
            values.add(head.val);
            head = head.next;
        }

        int n = values.size();
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            int val = values.get(i);

            while (!stack.isEmpty() && values.get(stack.peek()) < val) {
                res[stack.pop()] = val;
            }

            stack.push(i);
        }

        return res;
    }
}

func nextLargerNodes(head *ListNode) []int {
    // 栈中保存还没有找到下一个更大值的节点下标，且对应值保持单调递减。
    values := make([]int, 0)
    for head != nil {
        values = append(values, head.Val)
        head = head.Next
    }

    n := len(values)
    res := make([]int, n)
    stack := make([]int, 0)

    for i, val := range values {
        for len(stack) > 0 && values[stack[len(stack)-1]] < val {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = val
        }
        stack = append(stack, i)
    }

    return res
}

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

寻找右侧第一个小于等于当前价格的商品。栈保存待折扣下标，当前价格不大于栈顶价格时弹出并扣减；相等也有折扣，未结算的商品保持原价。

class Solution {
    public int[] finalPrices(int[] prices) {
        // 先按「无折扣」初始化，扫描结束后仍在栈里的元素自动保留原价。
        int[] res = prices.clone();
        // 栈里存下标：结算时既要写 res[idx] 又要读 prices[idx]。
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < prices.length; i++) {
            // 条件是 prices[j] <= prices[i]，相等也要算，所以弹栈用 >=。
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                int idx = stack.pop();

                res[idx] = prices[idx] - prices[i];
            }

            // 必须弹完再压，否则自己会把自己结算成 0。
            stack.push(i);
        }

        return res;
    }
}

func finalPrices(prices []int) []int {
    // 先按「无折扣」初始化，扫描结束后仍在栈里的元素自动保留原价。
    res := make([]int, len(prices))
    copy(res, prices)
    // 栈里存下标：结算时既要写 res[idx] 又要读 prices[idx]。
    stack := []int{}

    for i, price := range prices {
        // 条件是 prices[j] <= prices[i]，相等也要算，所以弹栈用 >=。
        for len(stack) > 0 && prices[stack[len(stack)-1]] >= price {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[idx] = prices[idx] - price
        }
        // 必须弹完再压，否则自己会把自己结算成 0。
        stack = append(stack, i)
    }

    return res
}

二、价格跨度

901. 股票价格跨度

栈保存价格和累计跨度，价格从栈底到栈顶严格递减。新价格大于等于栈顶时，弹出并合并对应跨度，再把当前价格与总跨度压栈；每个历史记录只进出栈一次。

class StockSpanner {
    // 栈存 [价格, 跨度]，价格从栈底到栈顶严格递减
    private final Deque<int[]> stack = new ArrayDeque<>();

    public StockSpanner() {}

    public int next(int price) {
        int span = 1;

        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            // 被吞并价格的跨度合并到当前价格上
            span += stack.pop()[1];
        }

        stack.push(new int[] {
            price,
            span
        });

        return span;
    }
}

type StockSpanner struct {
    // [价格, 跨度]，价格从栈底到栈顶严格递减
    stack [][2]int
}

func Constructor() StockSpanner {
    return StockSpanner{}
}

func (s *StockSpanner) Next(price int) int {
    span := 1
    for len(s.stack) > 0 && s.stack[len(s.stack)-1][0] <= price {
        // 被吞并价格的跨度合并到当前价格上
        span += s.stack[len(s.stack)-1][1]
        s.stack = s.stack[:len(s.stack)-1]
    }
    s.stack = append(s.stack, [2]int{
        price,
        span,
    })
    return span
}

三、矩形与雨水

84. 柱状图中最大的矩形

栈保存柱子下标，柱高从栈底到栈顶非递减。遇到更矮柱子时弹栈，以弹出柱高为矩形高度，用当前下标与新栈顶之间的距离计算宽度；等高柱子暂时留栈，由靠左的等高柱子最终覆盖更宽区间。末尾用高度为 0 的哨兵结算剩余候选。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] stack = new int[n];
        int top = -1;
        int ans = 0;

        for (int i = 0; i <= n; i++) {
            int cur = i == n ? 0 : heights[i];

            while (top >= 0 && heights[stack[top]] > cur) {
                int height = heights[stack[top--]];
                int left = top >= 0 ? stack[top] : -1;

                ans = Math.max(ans, height * (i - left - 1));
            }

            if (i < n) {
                stack[++top] = i;
            }
        }

        return ans;
    }
}

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0, len(heights))
    ans := 0

    for i := 0; i <= len(heights); i++ {
        cur := 0
        if i < len(heights) {
            cur = heights[i]
        }

        for len(stack) > 0 && heights[stack[len(stack)-1]] > cur {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            area := height * (i - left - 1)
            if area > ans {
                ans = area
            }
        }
        if i < len(heights) {
            stack = append(stack, i)
        }
    }
    return ans
}

85. 最大矩形

逐行累计每列连续为 1 的高度，遇到 0 就清零，将每一行转成柱状图最大矩形。每行用单调栈计算面积，再取全局最大值，空矩阵直接返回 0。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int[] heights = new int[matrix[0].length];
        int ans = 0;

        for (char[] row : matrix) {
            for (int col = 0; col < row.length; col++) {
                heights[col] = row[col] == '1' ? heights[col] + 1 : 0;
            }

            ans = Math.max(ans, largestRectangleArea(heights));
        }

        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        int[] stack = new int[heights.length + 1];
        int top = -1;
        int ans = 0;

        for (int i = 0; i <= heights.length; i++) {
            int current = i == heights.length ? 0 : heights[i];

            while (top >= 0 && heights[stack[top]] >= current) {
                int height = heights[stack[top--]];
                int left = top >= 0 ? stack[top] : -1;

                ans = Math.max(ans, height * (i - left - 1));
            }

            stack[++top] = i;
        }

        return ans;
    }
}

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    heights := make([]int, len(matrix[0]))
    ans := 0
    for _, row := range matrix {
        for col := range row {
            if row[col] == '1' {
                heights[col]++
            } else {
                heights[col] = 0
            }
        }
        if area := largestRectangleArea(heights); area > ans {
            ans = area
        }
    }
    return ans
}

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0, len(heights)+1)
    ans := 0

    for i := 0; i <= len(heights); i++ {
        current := 0
        if i < len(heights) {
            current = heights[i]
        }
        for len(stack) > 0 && heights[stack[len(stack)-1]] >= current {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            if area := height * (i - left - 1); area > ans {
                ans = area
            }
        }
        stack = append(stack, i)
    }
    return ans
}

42. 接雨水

栈保存高度非递增的柱子下标。遇到更高柱子时弹出凹槽底部，新栈顶和当前柱子分别作为左右挡板，按两侧较低高度与底部的差乘宽度，逐层累计水量；没有左挡板时不能接水。

class Solution {
    public int trap(int[] height) {
        int res = 0;
        // 存下标，高度从栈底到栈顶递减
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 凹槽底部
                int bottom = stack.pop();

                if (stack.isEmpty()) {
                    // 左边没有挡板，接不住水
                    break;
                }

                int left = stack.peek();
                int width = i - left - 1;
                int depth = Math.min(height[i], height[left]) - height[bottom];

                res += width * depth;
            }

            stack.push(i);
        }

        return res;
    }
}

func trap(height []int) int {
    res := 0
    // 存下标，高度从栈底到栈顶递减
    var stack []int

    for i, h := range height {
        for len(stack) > 0 && h > height[stack[len(stack)-1]] {
            // 凹槽底部
            bottom := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                // 左边没有挡板，接不住水
                break
            }
            left := stack[len(stack)-1]
            width := i - left - 1
            depth := min(h, height[left]) - height[bottom]
            res += width * depth
        }
        stack = append(stack, i)
    }
    return res
}

四、最小字典序

316. 去除重复字母

记录每个字符最后出现的位置和是否已入栈，用栈构造最小字典序结果。只有栈顶更大、且该字符后面还会出现时才能弹出；已选字符直接跳过，保证每种字符恰好保留一次。

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] last = new int[26];

        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        StringBuilder stack = new StringBuilder();
        boolean[] inStack = new boolean[26];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (inStack[c - 'a']) {
                continue;
            }

            // 栈顶更大且后面还会出现时，才能放心弹出
            while (stack.length() > 0
                    && c < stack.charAt(stack.length() - 1)
                    && last[stack.charAt(stack.length() - 1) - 'a'] > i) {
                inStack[stack.charAt(stack.length() - 1) - 'a'] = false;
                stack.deleteCharAt(stack.length() - 1);
            }

            stack.append(c);
            inStack[c - 'a'] = true;
        }

        return stack.toString();
    }
}

func removeDuplicateLetters(s string) string {
    var last [26]int
    for i := 0; i < len(s); i++ {
        last[s[i]-'a'] = i
    }

    var stack []byte
    var inStack [26]bool

    for i := 0; i < len(s); i++ {
        c := s[i]
        if inStack[c-'a'] {
            continue
        }
        // 栈顶更大且后面还会出现时，才能放心弹出
        for len(stack) > 0 && c < stack[len(stack)-1] && last[stack[len(stack)-1]-'a'] > i {
            inStack[stack[len(stack)-1]-'a'] = false
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, c)
        inStack[c-'a'] = true
    }
    return string(stack)
}

402. 移掉 K 位数字

从高位到低位扫描，当前数字更小时，在剩余删除额度内弹出前面更大的数字。扫描结束后若仍有额度，从尾部继续删除，再去掉前导零；结果为空时返回 0。

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stack = new StringBuilder();

        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);

            // 高位出现更小的数字时，删掉栈顶的大数字
            while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }

            stack.append(c);
        }

        // 额度没用完，从末尾删掉最大的几位
        stack.setLength(stack.length() - k);

        int start = 0;

        while (start < stack.length() && stack.charAt(start) == '0') {
            start++;
        }

        String res = stack.substring(start);

        return res.isEmpty() ? "0" : res;
    }
}

func removeKdigits(num string, k int) string {
    var stack []byte

    for i := 0; i < len(num); i++ {
        // 高位出现更小的数字时，删掉栈顶的大数字
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, num[i])
    }

    // 额度没用完，从末尾删掉最大的几位
    stack = stack[:len(stack)-k]

    start := 0
    for start < len(stack) && stack[start] == '0' {
        start++
    }
    if start == len(stack) {
        return "0"
    }
    return string(stack[start:])
}

1673. 找出最具竞争力的子序列

保留长度为 k 的最小字典序子序列，相当于允许删除 n - k 个元素。当前值更小时，只在删除额度允许时弹出栈顶；结果已满时跳过当前元素也消耗额度，保证最终恰好保留 k 个元素。

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int[] stack = new int[k];
        int size = 0;
        int remove = nums.length - k;

        for (int value : nums) {
            while (size > 0 && remove > 0 && stack[size - 1] > value) {
                size--;
                remove--;
            }

            if (size < k) {
                stack[size++] = value;
            } else {
                remove--;
            }
        }

        return stack;
    }
}

func mostCompetitive(nums []int, k int) []int {
    stack := make([]int, 0, k)
    remove := len(nums) - k

    for _, value := range nums {
        for len(stack) > 0 && remove > 0 && stack[len(stack)-1] > value {
            stack = stack[:len(stack)-1]
            remove--
        }
        if len(stack) < k {
            stack = append(stack, value)
        } else {
            remove--
        }
    }
    return stack
}

五、最大字典序

321. 拼接最大数

枚举两个数组分别选取多少位，用单调栈各自选出指定长度的最大字典序子序列，再进行贪心合并。首位相等时必须比较剩余后缀，不能只比较当前一位；最后取所有分配方案中的最大结果。

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int lower = Math.max(0, k - nums2.length);
        int upper = Math.min(k, nums1.length);
        int[] best = new int[k];

        for (int take1 = lower; take1 <= upper; take1++) {
            int[] part1 = maxSubsequence(nums1, take1);
            int[] part2 = maxSubsequence(nums2, k - take1);
            int[] candidate = merge(part1, part2);

            if (greater(candidate, 0, best, 0)) {
                best = candidate;
            }
        }

        return best;
    }

    private int[] maxSubsequence(int[] nums, int length) {
        int[] stack = new int[length];
        int top = 0;
        int drop = nums.length - length;

        for (int num : nums) {
            while (top > 0 && drop > 0 && stack[top - 1] < num) {
                top--;
                drop--;
            }

            if (top < length) {
                stack[top++] = num;
            } else {
                drop--;
            }
        }

        return stack;
    }

    private int[] merge(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        int index1 = 0;
        int index2 = 0;

        for (int i = 0; i < merged.length; i++) {
            if (greater(nums1, index1, nums2, index2)) {
                merged[i] = nums1[index1++];
            } else {
                merged[i] = nums2[index2++];
            }
        }

        return merged;
    }

    // 首位相等时比较剩余后缀，决定下一位来自哪条子序列。
    private boolean greater(int[] nums1, int index1, int[] nums2, int index2) {
        while (index1 < nums1.length && index2 < nums2.length && nums1[index1] == nums2[index2]) {
            index1++;
            index2++;
        }

        return index2 == nums2.length || (index1 < nums1.length && nums1[index1] > nums2[index2]);
    }
}

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    lower := 0
    if k-len(nums2) > lower {
        lower = k - len(nums2)
    }
    upper := k
    if len(nums1) < upper {
        upper = len(nums1)
    }

    best := make([]int, k)
    for take1 := lower; take1 <= upper; take1++ {
        part1 := maxSubsequence(nums1, take1)
        part2 := maxSubsequence(nums2, k-take1)
        candidate := mergeMax(part1, part2)
        if greaterSeq(candidate, 0, best, 0) {
            best = candidate
        }
    }
    return best
}

func maxSubsequence(nums []int, length int) []int {
    stack := make([]int, 0, length)
    drop := len(nums) - length

    for _, num := range nums {
        for len(stack) > 0 && drop > 0 &&
            stack[len(stack)-1] < num {
            stack = stack[:len(stack)-1]
            drop--
        }
        if len(stack) < length {
            stack = append(stack, num)
        } else {
            drop--
        }
    }
    return stack
}

func mergeMax(nums1 []int, nums2 []int) []int {
    merged := make([]int, len(nums1)+len(nums2))
    index1, index2 := 0, 0

    for i := range merged {
        if greaterSeq(nums1, index1, nums2, index2) {
            merged[i] = nums1[index1]
            index1++
        } else {
            merged[i] = nums2[index2]
            index2++
        }
    }
    return merged
}

// 首位相等时比较剩余后缀，决定下一位来自哪条子序列。
func greaterSeq(nums1 []int, index1 int, nums2 []int, index2 int) bool {
    for index1 < len(nums1) && index2 < len(nums2) &&
        nums1[index1] == nums2[index2] {
        index1++
        index2++
    }
    return index2 == len(nums2) ||
        (index1 < len(nums1) && nums1[index1] > nums2[index2])
}

六、区间贡献

907. 子数组的最小值之和

计算每个元素作为最小值时覆盖的子数组数量。当前值小于等于栈顶时弹栈，新栈顶给出左侧严格更小边界，当前位置给出右侧小于等于边界；贡献为元素值乘左右可选长度。一侧严格、一侧非严格，避免重复值重复计数。

class Solution {
    public int sumSubarrayMins(int[] arr) {
        final int MOD = 1_000_000_007;
        int n = arr.length;
        long res = 0;
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i <= n; i++) {
            // i == n 作为哨兵，把栈清空
            while (!stack.isEmpty() && (i == n || arr[stack.peek()] >= arr[i])) {
                int top = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();

                res = (res + (long) arr[top] * (top - left) * (i - top)) % MOD;
            }

            if (i < n) {
                stack.push(i);
            }
        }

        return (int) res;
    }
}

func sumSubarrayMins(arr []int) int {
    const mod = 1_000_000_007
    n := len(arr)
    res := 0
    // 单调递增栈，存下标
    var stack []int

    for i := 0; i <= n; i++ {
        // i == n 作为哨兵，把栈清空
        for len(stack) > 0 && (i == n || arr[stack[len(stack)-1]] >= arr[i]) {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            res = (res + arr[top]*(top-left)*(i-top)) % mod
        }
        if i < n {
            stack = append(stack, i)
        }
    }
    return res
}

七、排序边界

581. 最短无序连续子数组

正向扫描时，遇到更小值就弹出候选下标并更新最左重排位置；反向扫描时，遇到更大值更新最右重排位置。两个边界之间就是需要排序的最短区间，没有逆序时返回 0。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int left = n;
        int right = -1;
        Deque<Integer> stack = new ArrayDeque<>();

        // 从左往右：被弹出的下标右侧存在更小值，必须重排
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                left = Math.min(left, stack.pop());
            }

            stack.push(i);
        }

        stack.clear();

        // 从右往左：被弹出的下标左侧存在更大值，必须重排
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                right = Math.max(right, stack.pop());
            }

            stack.push(i);
        }

        return right > left ? right - left + 1 : 0;
    }
}

func findUnsortedSubarray(nums []int) int {
    n := len(nums)
    left, right := n, -1
    var stack []int

    // 从左往右：被弹出的下标右侧存在更小值，必须重排
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if top < left {
                left = top
            }
        }
        stack = append(stack, i)
    }

    stack = stack[:0]
    // 从右往左：被弹出的下标左侧存在更大值，必须重排
    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if top > right {
                right = top
            }
        }
        stack = append(stack, i)
    }

    if right <= left {
        return 0
    }
    return right - left + 1
}

八、模式检测

456. 132 模式

从右向左扫描，栈维护候选的“3”，另一个变量记录已确认的最大“2”。当前值大于栈顶时，弹出的较小值成为“2”的候选；在更左侧遇到比“2”还小的值，就构成下标有序、大小满足 1 < 2 < 3 的 132 模式。

class Solution {
    public boolean find132pattern(int[] nums) {
        // 候选的 "3"，从栈底到栈顶递减
        Deque<Integer> stack = new ArrayDeque<>();
        // 已确认的最大的 "2"
        int second = Integer.MIN_VALUE;

        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < second) {
                // nums[i] 就是 "1"
                return true;
            }

            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                second = stack.pop();
            }

            stack.push(nums[i]);
        }

        return false;
    }
}

import "math"

func find132pattern(nums []int) bool {
    // 候选的 "3"，从栈底到栈顶递减
    var stack []int
    // 已确认的最大的 "2"
    second := math.MinInt

    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] < second {
            // nums[i] 就是 "1"
            return true
        }
        for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
            second = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, nums[i])
    }
    return false
}

九、最大宽度坡

962. 最大宽度坡

正向扫描时，只把刷新前缀最小值的下标入栈，保留可能的左端点。再从右向左扫描，当前值不小于栈顶对应值时结算宽度并弹栈；从最右侧开始匹配，确保每个左端点首次匹配到的就是最宽结果。

class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        int[] stack = new int[n];
        int top = -1;

        // 只有创造了新前缀最小值的下标，才有资格当左端点。
        for (int i = 0; i < n; i++) {
            if (top == -1 || nums[i] < nums[stack[top]]) {
                stack[++top] = i;
            }
        }

        int answer = 0;

        // 从右往左，保证第一次匹配到的就是该左端点的最右伙伴。
        for (int j = n - 1; j >= 0; j--) {
            while (top >= 0 && nums[j] >= nums[stack[top]]) {
                answer = Math.max(answer, j - stack[top]);
                top--;
            }
        }

        return answer;
    }
}

func maxWidthRamp(nums []int) int {
    n := len(nums)
    stack := make([]int, 0, n)
    // 只有创造了新前缀最小值的下标，才有资格当左端点。
    for i := 0; i < n; i++ {
        if len(stack) == 0 || nums[i] < nums[stack[len(stack)-1]] {
            stack = append(stack, i)
        }
    }

    answer := 0
    // 从右往左，保证第一次匹配到的就是该左端点的最右伙伴。
    for j := n - 1; j >= 0; j-- {
        for len(stack) > 0 && nums[j] >= nums[stack[len(stack)-1]] {
            i := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if j-i > answer {
                answer = j - i
            }
        }
    }
    return answer
}

十、树的构造

654. 最大二叉树

按数组顺序构造节点，用递减栈维护候选父子关系。当前值更大时连续弹栈，最后弹出的节点作为当前节点的左子树；栈中仍有节点时，将当前节点接为栈顶的右子树。栈底是全局最大值，对应整棵树的根。

class Solution {
    // 线性单调栈能用一次扫描保持“候选父子关系”，避免每次在区间里重新找最大值。
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();

        for (int v : nums) {
            TreeNode cur = new TreeNode(v);
            TreeNode left = null;

            while (!stack.isEmpty() && stack.peek().val < v) {
                left = stack.pop();
            }

            cur.left = left;

            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }

            stack.push(cur);
        }

        // push 从头部入栈，栈底在尾部；栈底即全局最大值，也就是树根。
        return stack.peekLast();
    }
}

func constructMaximumBinaryTree(nums []int) *TreeNode {
    // 线性单调栈能用一次扫描保持“候选父子关系”，避免每次在区间里重新找最大值。
    stack := make([]*TreeNode, 0)
    for _, v := range nums {
        cur := &TreeNode{Val: v}
        var left *TreeNode
        for len(stack) > 0 && stack[len(stack)-1].Val < v {
            left = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        cur.Left = left
        if len(stack) > 0 {
            stack[len(stack)-1].Right = cur
        }
        stack = append(stack, cur)
    }
    // 切片头部是栈底，存放的正是全局最大值。
    return stack[0]
}

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/15969090

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！