题目链接

https://www.nowcoder.com/questionTerminal/1504075c856248748ca444c8c093d638?toCommentId=6413719
该题下的某题解是我写的，并没有抄袭搬运

题目

题目理解

简单的说就是在自己之前的且值比自己大的结点的下标，然后把这些下标相加求和

思路一：栈

• 栈用来存结点的下标
• 当栈不为空且a[栈顶下标]小于当前结点时，出栈，也就是说往前看坐标
  -出了第二步之后表明a[栈顶下标]已经比当前结点大了，可以求和了
• 保存当前结点的下标

---

这种解法要点在于保存每一个结点的下标用于下一个结点的大小比较
假如5，3，2
你不能因为5>3就把3的小标给扔了，会造成5>2，结果保存了5所在的下标

完整代码

import java.util.*;


public class Solution {
    public long  solve (int n, int[] a) {
        if(n<=1){
            return 0;
        }
        // write code here
        Stack<Integer> s=new Stack<>();

        long  score=0l;
        for(int i=0;i<n;i++){
            //寻找到大于当前结点的结点时退出
            while(!s.empty()&&a[s.peek()]<=a[i]){
                s.pop();
            }
            while(!s.empty()){
                score+=s.peek()+1;
            }
            //保存每一个下标
            s.push(i);
        }
        return score;
    }
}

---

思路二：暴力

import java.util.*;


public class Solution {
    public long  solve (int n, int[] a) {
        if(n<=1){
            return 0;
        }
        long score=0l;
        for(int i=0;i<n;i++)
            for(int j=i;j>=0;j--){
                if(a[j]>a[i]){
                    score+=j+1;
                    break;
                }
            }
        return score;
    }
}