刷题笔记合集🔗

转盘寿司

问题描述

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)])))

• C

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 500

// 单调栈结构
typedef struct {
    int data[MAX_N];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 压栈
void push(Stack* s, int val) {
    s->data[++s->top] = val;
}

// 出栈
void pop(Stack* s) {
    if (s->top >= 0) s->top--;
}

// 获取栈顶元素
int top(Stack* s) {
    return s->data[s->top];
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

int main() {
    int prices[MAX_N], res[MAX_N], n = 0;
    Stack stk;
    
    // 读取输入
    while (scanf("%d", &prices[n]) != EOF) {
        n++;
    }
    
    // 初始化结果数组和栈
    for (int i = 0; i < n; i++) {
        res[i] = 0;
    }
    initStack(&stk);
    
    // 第一次从右向左遍历，构建单调递增栈
    for (int i = n - 1; i >= 0; i--) {
        while (!isEmpty(&stk) && top(&stk) >= prices[i]) {
            pop(&stk);
        }
        push(&stk, prices[i]);
    }
    
    // 清空栈，准备第二次遍历
    initStack(&stk);
    
    // 第二次从右向左遍历，计算实际得到的总价格
    for (int i = n - 1; i >= 0; i--) {
        while (!isEmpty(&stk) && top(&stk) >= prices[i]) {
            pop(&stk);
        }
        if (!isEmpty(&stk)) {
            res[i] += top(&stk);
        }
        push(&stk, prices[i]);
    }
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        printf("%d ", prices[i] + res[i]);
    }
    printf("\n");
    
    return 0;
}

• Javascript

// 读取输入的函数
c