题目描述与示例
题目描述
寿司店周年庆,正在举办优惠活动回馈新老客户寿司转盘上总共有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++)⽬录汇总(每⽇更新)