思路一:

暴力破解

  • 对每个位置i,从后往前依次遍历[0, i-1],即依次遍历 i-1, i-2, ..., 0,找到比a[i]大的位置,更新荒唐度值
  • 复杂度:时间复杂度o(n^2),

思路二:

利用单调栈

  • 设置一个单调递减的栈,将a[i]与栈顶元素进行比较,若大于栈顶元素,则不断移除栈顶元素直至栈顶元素大于a[i]或者为空,然后更新荒唐度

  • 复杂度:时间复杂度o(n),空间复杂度o(n)

  • 本代码中栈中元素为索引值

    long long solve(int n, vector<int>& a) {
          // write code here
          if(n <= 1) return 0;
          stack<int> st;
          long long ans = 0;
          for(int i = 0; i < n; i++){
              while(!st.empty() && a[st.top()] <= a[i]){
                  st.pop();
              }
              if(!st.empty()){
                  ans += st.top() + 1;
              }
              st.push(i);
          }
    
          return ans;
      }