转盘寿司 - 华为OD统一考试

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

寿司店周年庆，正在举办优惠活动回馈新老用户。

寿司转盘上总共有 n 盘寿司， prices[i] 是第 i 盘寿司的价格。

如果客户选择了第 i 盘寿司，寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司 j ，前提是 prices[j] < prices[i]，如果没有满足条件的 i ，则不赠送寿司。

每个价格的寿司都可无限供应。

输入描述

输入的每一个数字代表寿司的价格，每盘寿司的价格之间使用空格分隔，例如：

3 15 6 14

表示:

第 0 盘寿司价格 prices[0] 为 3
第 1 盘寿司价格 prices[1] 为 15
第 2 盘寿司价格 prices[2] 为 6
第 3 盘寿司价格 prices[3] 为 14
寿司的盘数 n 范围为：1 ≤ n ≤ 500

每盘寿司的价格 price 范围为：1≤ price ≤1000

输出描述

输出享受优惠后的一组数据，每个值表示客户端选择第 i 盘寿司实际得到的寿司的总价格，使用空格进行分隔，例如：

3 21 9 17

示例1

输入：
3 15 6 14

输出：
3 21 9 17

题解

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

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

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

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

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

Java

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]) + " ");
        }
    }
}

Python

from collections import deque

prices = list(map(int, input().split()))
n = len(prices)

# gift[i] 表示免费赠送寿司价格
gift = [0] * n
# 大顶栈
st = deque()
for i in range(2 * n):
    idx = i % n

    # 当前价格小于栈顶价格时则出栈， 并维护免费赠送寿司价格
    while st and prices[st[-1]] > prices[idx]:
        pop_idx = st.pop()
        if gift[pop_idx] == 0:
            gift[pop_idx] = prices[idx]

    st.append(idx)

for i in range(n):
    print(prices[i] + gift[i], end=" ")

C++

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    vector<int> prices;
    int price;
    while(cin >> price) {
        prices.push_back(price);
    }
    int n = prices.size();

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

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

    for(int i = 0; i < n; i++) {
        cout << prices[i] + gift[i] << " ";
    }


    return 0;
}