Google电面面经

大概。。。这样？

1.     public boolean increasingTriplet(int[] nums) {
   
2.         if(nums == null || nums.length < 3) return false;
   
3.         int n = nums.length;
   
4.         int num1 = Integer.MAX_VALUE;
   
5.         int num2 = Integer.MAX_VALUE;
   
6.         for(int i = 0; i < n; i++){
   
7.             if(nums[i] <= num1){
   
8.                 num1 = nums[i];
   
9.             } else if(nums[i] <= num2){
   
10.                 num2 = nums[i];
    
11.             } else {
    
12.                 return true;
    
13.             }
    
14.         }
    
15.   
    
16.         return false;
    
17.     }

复制代码

补充内容 (2016-9-1 04:20):
大概意思就是维护一个 size = 3 的单调栈。。LIS 的常数退化版

ytsr 发表于 2016-9-1 04:09
你这个复杂度是 O（n^2）, longest increasing subsequence的解法在你这个最长为3的情况下复杂度是 O(n)

longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)

LC 334~~~

aangel 发表于 2016-8-31 15:30
longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)

三个变量a b c，一次循环
set a <- nums[0]
如果找到一个比a 大的就存在b上
如果找到一个比b 大的就存在c上

就酱w

补充内容 (2016-8-31 15:42):
酱你大爷，写错了6666

aangel 发表于 2016-9-1 04:30
longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)

这个需要存的序列最长为2，第3个出现就返回true了， 最坏也就O(2N) = O(N)

我的暴力是O(n^3)哈哈，水平不行啊。
我刚在二楼说的是印度小哥让我优化的思路，可能是看我水平实在不行就不要求o(n)了，优化到o(n^2)就可以了？？

我觉得确实有时候要跟着面试官，面试官有自己的一套解法，我们开始是讨论了半天解法，很浪费时间
后来是在说不明白了，他说那你先暴力吧，然后再优化。

是印度小哥，感觉还挺友好的。

chestnut9919 发表于 2016-9-1 04:36
LC 334~~~

就是这题，谢谢大神：）

没太多时间的话，近期的lc公司标签题还是要准备一下，还是挺合算的

这道题目是fb高频啊? 怎么 g拿来面试了

用patient sort O(n)

补充内容 (2016-9-5 23:34):
Patience sorting.
实际上是O(N*lgN)，但是最长长度是3，搜索过程变为常数，就是O(N)