转盘寿司 - 华为OD机试题

3 15 6 14

3 21 9 17

输入：
3 15 6 14

输出：
3 21 9 17

单调栈是一种特殊的栈数据结构，用于解决一类与找下一个更大或更小元素相关的问题。

在这个问题中，我们使用单调递减栈。

单调栈的基本思想是，维护一个栈，使得栈内的元素保持单调递减（或单调递增）。当新元素要入栈时，我们需要弹出栈内所有比该元素小的元素，以确保栈的单调性。这样，在栈中，每个元素的下一个更小（或更大）的元素就是它本身。

在这个问题中，我们用单调递减栈来维护右边第一个价格比当前寿司价格小的寿司位置。算法的步骤如下：

初始化一个空栈 st 和一个数组 gift，其中 gift[i] 表示免费赠送寿司价格，默认为 0。
从左到右遍历两倍的寿司列表，记当前索引为 idx。
如果栈 st 不为空且当前寿司价格 prices[idx] 小于栈顶寿司价格 prices[st.top()]，则出栈，维护免费赠送寿司价格。
将当前索引 idx 入栈。
遍历结束后，gift[i] 就是每盘寿司实际免费得到赠送寿司的价格。
然后打印输出每盘寿司实际得到的寿司的总价格即可。

import java.util.*;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> prices = new ArrayList<>();
        while (scanner.hasNextInt()) {
            prices.add(scanner.nextInt());
        }
        int n = prices.size();

        // gift[i] 表示免费赠送寿司价格
        int[] gift = new int[n];
        // 大顶栈
        Deque<Integer> st = new ArrayDeque<Integer>();
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;

            // 当前价格小于栈顶价格时则出栈， 并维护免费赠送寿司价格
            while (!st.isEmpty() && prices.get(st.peek()) > prices.get(idx)) {
                int popIdx = st.pop();
                if (gift[popIdx] == 0) {
                    gift[popIdx] = prices.get(idx);
                }
            }
            st.push(idx);
        }

        for (int i = 0; i < n; i++) {
            System.out.print((prices.get(i) + gift[i]) + " ");
        }
    }
}