转盘寿司 - 华为OD统一考试(D卷)
OD统一考试(D卷)
分值: 100分
题解: Java / Python / C++
题目描述
寿司店周年庆,正在举办优惠活动回馈新老用户。
寿司转盘上总共有 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] 表示免费赠送寿司价格
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。