最新华为OD机试真题-特惠寿司(100分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

感谢大家的订阅➕ 和 喜欢

在线评测链接

>= 特惠寿司(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

特惠寿司

问题描述

LYA 去一家寿司店吃饭，店里正在举办优惠活动。转盘上有 盘寿司，第 盘寿司的价格为 。如果 LYA 选择第 盘寿司，店家会免费赠送距离第 盘寿司最近的下一盘价格更低的寿司 （即 ）。如果不存在这样的寿司 ，则不赠送。每种价格的寿司数量无限。请问 LYA 选择每盘寿司，最终实际得到的寿司总价格分别是多少？

输入格式

输入一行，包含 个空格分隔的正整数，表示 盘寿司的价格 。

输出格式

输出一行，包含 个空格分隔的正整数，第 个数表示 LYA 选择第 盘寿司实际得到的寿司总价格。

样例输入

3 15 6 14

样例输出

3 21 9 17

数据范围

题解

可以使用单调栈来解决这个问题。从右向左遍历寿司价格数组，对于每个寿司 ，找到右侧第一个价格小于它的寿司 ，那么实际得到的总价格就是 。

具体步骤如下：

1. 创建一个数组 ，用于存储每盘寿司实际得到的总价格，初始值为 。

2. 创建一个单调栈 ，用于存储寿司的价格。

3. 从右向左遍历寿司价格数组：

   • 如果栈不为空且栈顶元素大于等于当前寿司价格，则弹出栈顶元素，直到栈为空或栈顶元素小于当前价格。
   • 将当前寿司价格压入栈中。

4. 再次从右向左遍历寿司价格数组：

   • 如果栈不为空且栈顶元素大于等于当前寿司价格，则弹出栈顶元素，直到栈为空或栈顶元素小于当前价格。
   • 如果此时栈不为空，说明找到了右侧第一个价格小于当前寿司的寿司，将栈顶元素加到 上。
   • 将当前寿司价格压入栈中。

5. 遍历结束后， 中存储的就是选择第 盘寿司实际得到的总价格。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

prices = list(map(int, input().split()))
n = len(prices)
res = [0] * n
stk = []

for i in range(n - 1, -1, -1):
    while stk and stk[-1] >= prices[i]:
        stk.pop()
    stk.append(prices[i])
    
for i in range(n - 1, -1, -1):
    while stk and stk[-1] >= prices[i]:
        stk.pop()
    if stk:
        res[i] += stk[-1]
    stk.append(prices[i])

print(' '.join(map(str, [prices[i] + res[i] for i in range(n)])))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] pricesStr = sc.nextLine().split(" ");
        int n = pricesStr.length;
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = Integer.parseInt(pricesStr[i]);
        }
        
        int[] res = new int[n];
        Deque<Integer> stk = new ArrayDeque<>();
        
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.isEmpty() && stk.peekLast() >= prices[i]) {
                stk.pollLast();
            }
            stk.offerLast(prices[i]);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.isEmpty() && stk.peekLast() >= prices[i]) {
                stk.pollLast();
            }
            if (!stk.isEmpty()) {
                res[i] += stk.peekLast();
            }
            stk.offerLast(prices[i]);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(prices[i] + res[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

• Cpp

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    vector<int> prices;
    int price;
    while (cin >> price) {
        prices.push_back(price);
    }
    
    int n = prices.size();
    vector<int> res(n, 0);
    stack<int> stk;
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && stk.top() >= prices[i]) {
            stk.pop();
        }
        stk.push(prices[i]);
    }
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && stk.top() >= prices[i]) {
            stk.pop();
        }
        if (!stk.empty()) {
            res[i] += stk.top();
        }
        stk.push(prices[i]);
    }
    
    for (int i = 0; i < n; i++) {
        cout << prices[i] + res[i] << " ";
    }
    cout << endl;
    
    return 0;
}