枪打出头鸟
枪打出头鸟
http://www.nowcoder.com/questionTerminal/1504075c856248748ca444c8c093d638
思路一：
暴力破解
- 对每个位置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; }
