636. 132 Pattern

好题,用一个堆栈可以做到这个份上我也服了。

先说本题可以按照直接的思路来遍历数组,每个数字先找后面比他大的在找一个在两者之间的。但是利用堆栈来做本题简直是神奇。

维护一个堆栈,保存在栈里的数字都是132里面的2nd,再维护一个变量代表132里面的3rd。首先3rd初始化为INT_MIN。然后从后往前地遍历数组,如果栈为空或者当前数字大于栈顶,就把栈顶pop并赋值赋给3rd,然后入栈。如果当前数字小于3rd,即我们已找到了132的所有数字,当前数字即使1st。栈里的数字时刻保持都比3rd要大,所以当我们找到了第一个比3rd小的即为1st则游戏结束。

int third = Integer.MIN_VALUE;
 
 
 for(int i=nums.length-1; i>=0; i — ){
 if(nums[i]<third){
 return true;
 }
 else{
 while(!s.isEmpty() && nums[i]>s.peek()){
 third = s.pop();
 }
 s.push(nums[i]);
 }
 }
 
 return false;

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.