题型：单调栈

739. 每日温度

public int[] dailyTemperatures(int[] temperatures) {
    Deque<Integer> st = new ArrayDeque<>();
    int n = temperatures.length;
    int[] ans = new int[n];

    for (int i = n - 1; i >= 0; i--){
        int cur = temperatures[i];
        // 把所有小于当日气温的元素弹出栈
        while (!st.isEmpty() && cur >= temperatures[st.peek()]){
            st.pop();
        }
        // 如果栈不为空，栈顶元素是第一个高于当日气温的索引
        if (!st.isEmpty()){
            ans[i] = st.peek() - i;
        }
        st.push(i);
    }
    return ans;
}

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

public int[] finalPrices(int[] prices) {
    int n = prices.length;
    Deque<Integer> st = new ArrayDeque<>();
    int[] ans = new int[n];
    // 从后向前遍历
    for (int i = n - 1; i >= 0; i--) {
        int cur = prices[i];
        // 把栈中大于当前价格的元素都弹出栈
        while (!st.isEmpty() && st.peek() > cur) {
            st.pop();
        }
        // 栈不为空，则栈顶元素就是第一个 <= 当前价格的元素
        ans[i] = st.isEmpty() ? cur : cur - st.peek();
        // 把当前价格入栈
        st.push(cur);
    }
    return ans;
}

496. 下一个更大元素 I

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    Map<Integer, Integer> map = new HashMap<>(m);
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = m - 1; i >= 0; i--){
        int cur = nums2[i];
        // 弹出栈中所有小于等于 cur 的元素
        while (!st.isEmpty() && st.peek() <= cur){
            st.pop();
        }
        // 使用哈希表记录右侧第一个比 cur 大的元素
        map.put(cur, st.isEmpty() ? -1 : st.peek());
        st.push(cur);
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; i++){
        ans[i] = map.get(nums1[i]);
    }
    return ans;
}