题面描述

给定一个长度为$n$的数组，每个元素的“美好值”是该位置之前最近的、值小于等于当前值的元素，如果没有这样的元素，则美好值为0。最终要求计算所有位置的美好值总和。输入格式为第一行一个整数$n$，表示数组长度，第二行包含$n$个整数，表示数组元素。输出为一个整数，表示美好值的总和。

思路：单调栈

本题题目意思可以转为找到左边第一个比它小的数，因此可以使用单调栈来求解该问题

题解

在这个问题中，我们需要计算每个位置的“美好值”，它表示的是该位置左边最近的、且值小于等于该位置值的元素。如果不存在这样的元素，则美好值为0。这个问题可以转化为寻找每个位置左边第一个比当前元素小的数。

为了解决这个问题，我们可以使用单调栈。单调栈是一种特殊的栈数据结构，在栈中保持元素的单调性。具体来说，我们在这个问题中需要一个单调递增的栈来存储数组中的元素。

实现步骤

1. 初始化：创建一个栈用于存储元素，并初始化结果变量为0。
2. 遍历数组：对于数组中的每个元素：
   • 当栈不为空且栈顶元素大于当前元素时，弹出栈顶元素。这是为了保持栈的单调性。
   • 如果栈不为空，说明栈顶元素就是左边第一个小于等于当前元素的值，将这个值累加到结果中。
   • 将当前元素压入栈中。
3. 输出结果：最后输出结果的总和。

时间复杂度

$O(n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    cin >> n;  // 输入数组的长度
    long long res = 0;  // 用于保存美好值的总和
    stack<int> stk;  // 单调栈，用于存储元素

    // 遍历数组
    for (int i = 0; i < n; i++) {
        cin >> x;  // 输入当前元素
        
        // 保持栈的单调性，弹出栈顶大于当前元素的所有元素
        while (!stk.empty() && stk.top() > x) {
            stk.pop();
        }

        // 如果栈不为空，说明找到了左边第一个小于等于当前元素的值
        if (!stk.empty()) {
            res += stk.top();  // 累加该值到结果中
        }

        // 将当前元素压入栈中
        stk.push(x);
    }

    // 输出美好值的总和
    cout << res << endl;
    return 0;
}

python代码

# 输入数组的长度
n = int(input())
# 输入数组元素并转为整数列表
nums = list(map(int, input().split()))
# 反转数组，使得可以使用栈找出左边第一个小于等于当前元素的值
nums.reverse()

# 初始化栈，用于存储索引
stack = []
# 初始化美好值的总和
ans = 0

# 遍历反转后的数组
for i, num in enumerate(nums):
    # 当栈不为空且当前元素小于等于栈顶索引对应的元素时，弹出栈顶
    while len(stack) > 0 and num <= nums[stack[-1]]:
        stack.pop()  # 弹出栈顶元素
        ans += num   # 将当前元素累加到美好值总和中
    
    # 将当前元素的索引压入栈中
    stack.append(i)

# 输出美好值的总和
print(ans)

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建输入扫描器
        Scanner in = new Scanner(System.in);
        
        // 读取数组长度
        int n = in.nextInt();
        // 创建数组以存储输入的整数
        int[] a = new int[n];
        
        // 读取数组元素
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        
        // 初始化美好值的总和
        long res = 0;
        // 使用双端队列作为栈来存储元素
        Deque<Integer> stack = new LinkedList<>();
        
        // 从数组末尾向前遍历
        for (int i = n - 1; i >= 0; i--) {
            // 当栈不为空且当前元素小于等于栈顶元素时，弹出栈顶元素
            while (!stack.isEmpty() && a[i] <= stack.peek()) {
                stack.pop();  // 弹出栈顶元素
                res += a[i];  // 将当前元素累加到美好值总和中
            }
            // 将当前元素压入栈中
            stack.push(a[i]);
        }
        
        // 输出美好值的总和
        System.out.println(res);
    }
}

题目描述

给一定一个数组，每个位置的美好值是离该位置最近的且下标小于该位置，值小于等于该值的值，若没有则为0。求所有位置的美好值总和。

输入描述

第一行一个整数$n$，表示数组长度。$(1 \leq n \leq 10^5)$

接一行下来$n$个整数，表示该数组。$(1 \leq a[i] \leq 10^5)$

输出描述

输出一个整数，表示美好值的总和

样例

输入

5
2 3 4 1 5

输出

6

说明

0号位置前面没有值，美好值为0

1号位置前面最近小于等于的值为2，美好值为2

2号位置前面最近小于等于的值为3，美好值为3

3号位置前面没有小于等于该值的数，美好值为0

4号位置前面最近小于等于的值为1，美好值为1

总的美好值为$2+3+1=6$