题目描述与示例

题目描述

寿司店周年庆，正在举办优惠活动回馈新老客户寿司转盘上总共有n盘寿司，prices[i]是第 i 盘寿司的价格，如果客户选择了第 i盘寿司，寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司 j，前提是prices[j] < prices[i]，如果没有满足条件的 j，则不赠送寿司。 每个价格的寿司都可无限供应。

输入描述

输入的每一个数字代表每盘寿司的价格，每盘寿司的价格之间使用空格分隔 寿司的盘数 n范围为: 1 <= n <= 500

输出描述

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

示例一

输入

3 15 6 14

输出

3 21 9 17

示例二

输入

5 12 7 13

输出

5 19 12 18

解题思路

本题是在环型数组中计算每一个元素右侧的下一个更小元素，显然应该使用单调栈来完成。本题和LeetCode503. 下一个更大元素II的方法非常类似。

处理环型数组，可以将数组nums进行拼接，然后索引遍历的范围在[0, 2*n-1]进行即可。

PS：由于数据范围最多只有500，所以O(n^2)的暴力解是可以接受的。不熟悉单调栈的同学在考试遇到可以尝试使用暴力解。

代码

解法一：正序遍历写法

Python

# 题目：【单调栈】2023C-回转寿司
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：单调栈/正序遍历写法
# 代码看不懂的地方，请直接在群上提问

# 正序遍历写法
nums = list(map(int, input().split()))
n = len(nums)
stack = list()
# 初始化答案列表为nums的一个拷贝
# 这样对于数组中的最小值就不用额外考虑了
ans = nums.copy()
# 正序遍历下标
# 范围从0开始，到2*n-1结束
for i in range(2*n):
    # i对n求余，得到数字在nums中的真实下标
    idx = i % n
    num = nums[idx]
    while stack and nums[stack[-1]] > num:
        # 如果此时栈不为空，则栈顶元素top_idx索引右侧的下一个更小元素是nums[idx]
        # 因此ans[top_idx]为两者相加；否则只为nums[top_idx]
        top_idx = stack.pop()
        ans[top_idx] = num + nums[top_idx]
    stack.append(idx)

# 用解包的方式输出答案
print(*ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int n = input.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        Stack<Integer> stack = new Stack<>();
        int[] ans = Arrays.copyOf(nums, n);

        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            int num = nums[idx];
            while (!stack.isEmpty() && nums[stack.peek()] > num) {
                int topIdx = stack.pop();
                ans[topIdx] = num + nums[topIdx];
            }
            stack.push(idx);
        }

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

C++

“`C++
#include <iostream>
#include <sstream>
#include <vector>
#include <stack>

using namespace std;

int main() {
string input;
getline(cin, input);
stringstream ss(input);
vector<int> nums;
int num;
while (ss >> num) {
nums.push_back(num);
}
int n = nums.size();
stack<int> st;
vector<int> ans(nums.begin(), nums.end());

<pre><code>for (int i = 0; i < 2 * n; i++) {
int idx = i % n;
int num = nums[idx];
while (!st.empty() && nums[st.top()] > num) {
int topIdx = st.top();
st.pop();
ans[topIdx] = num + nums[topIdx];
}
st.push(idx);
}

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

return 0;
</code></pre>

}

<pre><code class="">## 解法二：逆序遍历写法

### Python

“`Python
# 题目：【单调栈】2023C-回转寿司
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：单调栈/逆序遍历写法
# 代码看不懂的地方，请直接在群上提问

# 逆序遍历写法
nums = list(map(int, input().split()))
n = len(nums)
stack = list()
# 初始化答案列表为nums的一个拷贝
# 这样对于数组中的最小值就不用额外考虑了
ans = nums.copy()
# 逆序遍历下标
# 范围从2*n-1开始，到0结束
for i in range(2*n-1, -1, -1):
# i对n求余，得到数字在nums中的真实下标
idx = i % n
num = nums[idx]
while stack and nums[stack[-1]] >= num:
stack.pop()
# 如果此时栈不为空，则栈顶是idx右侧的下一个更小元素的索引
# 因此ans[idx]为两者相加；否则只为nums[idx]
if stack:
ans[idx] = nums[stack[-1]] + nums[idx]
stack.append(idx)

# 用解包的方式输出答案
print(*ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] inputs = scanner.nextLine().split(" ");
        int[] nums = new int[inputs.length];
        for (int i = 0; i < inputs.length; i++) {
            nums[i] = Integer.parseInt(inputs[i]);
        }
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] ans = Arrays.copyOf(nums, n);

        for (int i = 2 * n - 1; i >= 0; i--) {
            int idx = i % n;
            int num = nums[idx];
            while (!stack.isEmpty() && nums[stack.peekLast()] >= num) {
                stack.pollLast();
            }
            if (!stack.isEmpty()) {
                ans[idx] = nums[stack.peekLast()] + nums[idx];
            }
            stack.offerLast(idx);
        }

        for (int num : ans) {
            System.out.print(num + " ");
        }
    }
}

C++

“`C++
#include <iostream>
#include <sstream>
#include <vector>
#include <stack>

using namespace std;

int main() {
string input;
getline(cin, input);
stringstream ss(input);
vector<int> nums;
int num;
while (ss >> num) {
nums.push_back(num);
}
int n = nums.size();
stack<int> stk;
vector<int> ans = nums;

<pre><code>for (int i = 2 * n – 1; i >= 0; –i) {
int idx = i % n;
int num = nums[idx];
while (!stk.empty() && nums[stk.top()] >= num) {
stk.pop();
}
if (!stk.empty()) {
ans[idx] = nums[stk.top()] + nums[idx];
}
stk.push(idx);
}

for (int i = 0; i < n; ++i) {
cout << ans[i] << " ";
}
return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(N)。循环遍历长度为2N的数组，每个元素只会出栈和入栈至多一次。

空间复杂度：O(N)。单调栈所占空间。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

上一篇 【单调栈】2023B-阿里巴巴找黄金宝箱(4)
下一篇 【单调栈】2023Q1A-天然蓄水池

相关文章