有效序列的数量

import java.io.*;
import java.util.*;

class Node {
    public int value;
    public int times;
    public Node(int v, int t) {
        value = v;
        times = t;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n < 2){
            System.out.println(0);
            return;
        }
        String[] strs = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(strs[i]);
        }
        long ans = 0;
        Stack<Node> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && stack.peek().value > arr[i]){
                Node topNode = stack.pop();
                ans += topNode.times + cn2(topNode.times);
            }
            if(!stack.isEmpty() && arr[i] == stack.peek().value){
                stack.peek().times++;
            }else{
                stack.push(new Node(arr[i], 1));
            }
        }
        while(!stack.isEmpty()){
            ans += cn2(stack.pop().times);
        }
        for(int i = n - 1; i >= 0; i--){
            while(!stack.isEmpty() && stack.peek().value > arr[i]){
                Node topNode = stack.pop();
                ans += topNode.times;
            }
            if(!stack.isEmpty() && arr[i] == stack.peek().value){
                stack.peek().times++;
            }else{
                stack.push(new Node(arr[i], 1));
            }
        }
        System.out.println(ans);
    }
    
    private static long cn2(int n) {
        return (long)n*(n - 1) >> 1;
    }
}

复杂度分析

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;
const int maxsize = 100019;
int stk[maxsize], n, top = 0, dp[maxsize];
long long ans = 0;

int main()
{
	int i, x, h, j;
	cin >> n;
	dp[0] = -1;
	for (i = 0; i < n; i++)
	{
		cin >> x;
		h = top;
		while (top > 0 && stk[top - 1] > x)
		{
			top = dp[top - 1] + 1;
		}
		j = top - 1;
		if (j > -1 && stk[j] == x) j = dp[j];
		ans += h - ((j == -1) ? 0 : j);
		dp[top] = j;
		stk[top++] = x;
	}
	cout << ans << endl;
}

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

int main() {
    int n;
    long long ans = 0;
    cin >> n;
    vector<int> st;
    vector<int> s;
    for(int i = 0; i < n; ++i) {
        int num;
        cin >> num;        
        if(!st.empty()) {
            int b = 0, e = st.size() - 1;
            while(b < e) {
                int m = (b + e)/2;
                if(s[st[m]] < num) {
                    b = m + 1;
                } else {
                    e = m;
                }
            }
            while(b > 0 && s[st[b]] >= num) b--;
            if(b >= 0) {
                ans += st.size() - b;
            }
        }
        while(!st.empty() && s[st.back()] > num) {
            st.pop_back();
        }
        st.push_back(i);
        s.push_back(num);
    }
    cout << ans << endl;
}
// 64 位输出请用 printf("%lld")

• 根据单调栈的知识，能联想到如果遇到一个小的数，那么在它前面比它大的数可以不要了，所以是单调递增栈。
• 但最核心的难点在于，本题很难确定是严格的单调递增栈，还是非严格的单调递增栈。也就是说，遇到重复元素到底如何处理。
• 用几个test case尝试，比如当前栈是1，3，3，后面如果来了一个3，可以和3个数都组成有效序列。result要加上3，所以重复元素信息不能丢，为非严格的单调递增栈。但而不把3出栈，怎么知道前面有没有1呢，因为如果当前栈是3，3，没有1，当前result只用加2，所以3还是得都出栈，看栈是否为空，只不过丢掉的3都得重新入栈。
• 分析到这里，逻辑就很清晰了。该单调栈一定得记录重复元素信息，为非严格的，每次更新result的时候要出栈所有重复，看栈是否为空，然后加回重复。
• 但是上述解法虽然可以解决，但就不满足单调栈的性质了，因为每个元素不只是被入栈出栈一遍，最差的情况有可能是n遍，复杂度到了O(n^2)
• 用一个技巧，放入栈的元素改为2维数组，一个是元素，另一个记录其个数，这样重复出栈的时候只用判断栈的size是否大于1，而不用真的把该元素出栈了。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        in.nextLine();
        String[] str = in.nextLine().split(" ");
        int[] input = new int[n];

        for (int i = 0; i < str.length; i++) {
            input[i] = Integer.valueOf(str[i]);
        }

        Deque<int[]> stack = new ArrayDeque<>();
        long result = 0;

        for (int i = 0; i < input.length; i++) {
            int val = input[i];
            while (!stack.isEmpty() && val < stack.peekLast()[0]) {
                int[] cur = stack.pollLast();
                result += cur[1];
            }
            if (stack.isEmpty()) {
                stack.offerLast(new int[]{val, 1});
            } else {
                int[] cur = stack.peekLast();
                if (val == cur[0]) {
                    result += cur[1];
                    cur[1]++;
                    if (stack.size() > 1) {
                        result++;
                    }

                } else { // if val > cur[0]
                    result++;
                    stack.offerLast(new int[]{val, 1});
                }
            }
        }
        System.out.println(result);
    }
}

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> nums(n, 0);
	vector<int> v_stack;
	vector<int> dp(n, 0);
	long long ans = 0;
	int top = -1;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		nums[i] = x;


	}
	int h = 0;
	for (int i = 0; i < n; ++i) {
		if (top >= 0) {
			if (nums[v_stack[top]] >= nums[i]) {
				while (top >= 0 && nums[v_stack[top]] > nums[i]) {

					++h;
					v_stack.pop_back();
					--top;
				}
				if (top >= 0) {
					if (nums[v_stack[top]] == nums[i]) {
						dp[i] = dp[v_stack[top]] + 1;
						h += dp[i];
						if(top >= dp[i]){
							++h;
						}
					}else{
						++h;
					}
				}
			}
		}
		v_stack.push_back(i);
		++top;
		if (i > 0) {
			h = h ? h : 1;
			ans += h;
		}
		h = 0;
	}
	cout << ans << endl;
	return 0;
}