https://leetcode.com/discuss/interview-question/742523/facebook-prep-question-contiguous-subarrays-on-solution

 

 1 int[] countSubarrays(int[] arr) {
 2     int len = arr.length;
 3     
 4     Deque<Integer> stack = new ArrayDeque<>(); //index
 5     int[] leftCount = new int[len];
 6     //left[0] = 0
 7     stack.addLast(0);
 8     for(int i = 1; i<len; ++i) {
 9       int current = arr[i];
10       if(arr[stack.peekLast()]>current){
11         leftCount[i] = 0;
12         stack.addLast(i);
13         continue;
14       }
15       
16       while(!stack.isEmpty() && arr[stack.peekLast()]<current){
17         stack.removeLast();
18       }
19       int last = -1;
20       if(!stack.isEmpty()) {
21         last = stack.peekLast();
22       }
23       leftCount[i] = i - (last+1);
24       stack.addLast(i);
25     }
26     
27     stack.clear();
28     stack.addLast(len-1);
29     int[] rightCount = new int[len];
30     for(int i = len-2; i>=0; --i) {
31       int current = arr[i];
32       if(arr[stack.peekLast()]>current){
33         rightCount[i] = 0;
34         stack.addLast(i);
35         continue;
36       }
37       
38       while(!stack.isEmpty() && arr[stack.peekLast()]<current){
39         stack.removeLast();
40       }
41       int last = len;
42       if(!stack.isEmpty()) {
43         last = stack.peekLast();
44       }
45       rightCount[i] = last-1-i;
46       stack.addLast(i);
47     }
48     
49     int[] ret = new int[len];
50     for(int i = 0; i<len; ++i) {
51       ret[i] = leftCount[i] + rightCount[i] + 1;
52     }
53     return ret;
54   }