单调栈

• OI Wiki: https://oi-wiki.org/ds/monotonous-stack/

题目	难度
907. 子数组的最小值之和	中等	数据范围 3*10^4
1508. 子数组和排序后的区间和	中等	数据范围 1e3 O(n^2) 优化至 O(n)
1856. 子数组最小乘积的最大值	中等	数据范围 1e5
2104. 子数组范围和	中等	数据范围 1e3 O(n^2) 优化至 O(n)
2281. 巫师的总力量和	困难	数据范围 1e5

题目	难度
316. 去除重复字母	中等	去重、字典序最小
221021 天池-03. 整理书架	中等	数量不大于 limit、最小排列

区间问题

907. 子数组的最小值之和

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Solution907 {
    private static final long MOD = 1000000007;

    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;

        // step1: 求左侧第一个 "严格小于" arr[i] 的下标，如没有则为 -1
        Deque<Integer> stack1 = new ArrayDeque<>();
        int[] left = new int[n];
        Arrays.fill(left, -1);
        for (int i = 0; i < n; i++) {
            while (!stack1.isEmpty() && arr[i] <= arr[stack1.peek()]) {
                stack1.pop();
            }
            if (!stack1.isEmpty()) {
                left[i] = stack1.peek();
            }
            stack1.push(i);
        }

        // step2: 求右侧第一个 "小于等于" arr[i] 的下标，如没有则为 n
        Deque<Integer> stack2 = new ArrayDeque<>();
        int[] right = new int[n];
        Arrays.fill(right, n);
        for (int i = n - 1; i >= 0; i--) {
            // <= 为避免重复计算
            while (!stack2.isEmpty() && arr[i] < arr[stack2.peek()]) {
                stack2.pop();
            }
            if (!stack2.isEmpty()) {
                right[i] = stack2.peek();
            }
            stack2.push(i);
        }

        long sum = 0;
        for (int i = 0; i < n; i++) {
            long cnt = (long) (i - left[i]) * (right[i] - i) % MOD;
            sum += arr[i] * cnt % MOD;
            sum %= MOD;
        }
        return (int) sum;
    }
}

字典序最小

316. 去除重复字母

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution316 {
    public String removeDuplicateLetters(String s) {
        // 右侧（含自身）元素频次
        int[] cntArr = new int[26];
        for (char ch : s.toCharArray()) {
            cntArr[ch - 'a']++;
        }

        // 栈中元素频次
        int[] stackArr = new int[26];
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            // 无法入栈
            if (stackArr[ch - 'a'] == 1) {
                cntArr[ch - 'a']--;
                continue;
            }
            // 栈顶元素能出栈
            while (!stack.isEmpty() && stack.peek() > ch && cntArr[stack.peek() - 'a'] > 1) {
                char pop = stack.pop();
                cntArr[pop - 'a']--;
                stackArr[pop - 'a']--;
            }
            stack.push(ch);
            stackArr[ch - 'a']++;
        }

        int sz = stack.size();
        char[] chars = new char[sz];
        for (int i = sz - 1; i >= 0; i--) {
            chars[i] = stack.pop();
        }
        return new String(chars);
    }
}

221021 天池-03. 整理书架

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Tianchi221022T3 {
    public int[] arrangeBookshelf(int[] order, int limit) {
        // 右侧（含自身）元素频次
        Map<Integer, Integer> cntMap = new HashMap<>();
        for (int x : order) {
            cntMap.put(x, cntMap.getOrDefault(x, 0) + 1);
        }
        // 栈中元素频次
        Map<Integer, Integer> stackMap = new HashMap<>();

        Deque<Integer> stack = new ArrayDeque<>();
        for (int x : order) {
            // 无法入栈
            if (stackMap.getOrDefault(x, 0) == limit) {
                cntMap.put(x, cntMap.get(x) - 1);
                continue;
            }

            // 栈顶元素能出栈
            while (!stack.isEmpty() && stack.peek() > x && cntMap.get(stack.peek()) > limit) {
                int pop = stack.pop();
                cntMap.put(pop, cntMap.get(pop) - 1);
                stackMap.put(pop, stackMap.get(pop) - 1);
            }

            stack.push(x);
            stackMap.put(x, stackMap.getOrDefault(x, 0) + 1);
        }

        // => int[]
        int sz = stack.size();
        int[] res = new int[sz];
        for (int i = sz - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}

（全文完）