有效序列的数量

• 根据单调栈的知识，能联想到如果遇到一个小的数，那么在它前面比它大的数可以不要了，所以是单调递增栈。
• 但最核心的难点在于，本题很难确定是严格的单调递增栈，还是非严格的单调递增栈。也就是说，遇到重复元素到底如何处理。
• 用几个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);
    }
}

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;
    }
}

复杂度分析