LeetCode 334 - Increasing Triplet Subsequence


[LeetCode]Increasing Triplet Subsequence | 书影博客
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < kn-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.

题目大意:

给定一个无序数组,判断其中是否存在一个长度为3的递增序列。
形式上,函数应当:
如果存在这样的i, j, k(0 ≤ i < j < k ≤ n-1),使得arr[i] < arr[j] < arr[k],返回true,否则返回false。
你的算法应当满足O(n)时间复杂度和O(1)空间复杂度。
def increasingTriplet(self, nums): a = b = None for n in nums: if a is None or a >= n: a = n elif b is None or b >= n: b = n else: return True return False

https://leetcode.com/discuss/86891/concise-java-solution-with-comments
public boolean increasingTriplet(int[] nums) { // start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true. int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE; for (int n : nums) { if (n <= small) { small = n; } // update small if n is smaller than both else if (n <= big) { big = n; } // update big only if greater than small but smaller than big else return true; // return if you find a number bigger than both } return false; }
https://leetcode.com/discuss/86593/clean-and-short-with-comments-c
bool increasingTriplet(vector<int>& nums) { int c1 = INT_MAX, c2 = INT_MAX; for (int x : nums) { if (x <= c1) { c1 = x; // c1 is min seen so far (it's a candidate for 1st element) } else if (x <= c2) { // here when x > c1, i.e. x might be either c2 or c3 c2 = x; // x is better than the current c2, store it } else { // here when we have/had c1 < c2 already and x > c2 return true; // the increasing subsequence of 3 elements exists } } return false; }
X.
https://leetcode.com/discuss/86954/just-a-simplified-version-of-patient-sort
https://leetcode.com/discuss/87204/accepted-java-solution-this-question-only-lines-clear-concise
The main idea is keep two values when check all elements in the array: the minimum value minuntil now and the second minimum value secondMin from the minimum value's position until now. Then if we can find the third one that larger than those two values at the same time, it must exists the triplet subsequence and return true.
What need to be careful is: we need to include the condition that some value has the same value with minimum number, otherwise this condition will cause the secondMin change its value.
    public boolean increasingTriplet(int[] nums) {
        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
        for(int num : nums){
            if(num <= min) min = num;
            else if(num < secondMin) secondMin = num;
            else if(num > secondMin) return true;
        }
        return false;
    }
http://www.programcreek.com/2015/02/leetcode-increasing-triplet-subsequence-java/
This problem can be converted to be finding if there is a sequence such thatthe_smallest_so_far < the_second_smallest_so_far < current. We use x, y and z to denote the 3 number respectively.
public boolean increasingTriplet(int[] nums) {
 int x = Integer.MAX_VALUE;
 int y = Integer.MAX_VALUE;
 
 for (int i = 0; i < nums.length; i++) {
  int z = nums[i];
 
  if (x >= z) {
   x = z;// update x to be a smaller value
  } else if (y >= z) {
   y = z; // update y to be a smaller value
  } else {
   return true;
  }
 }
 
 return false;
}
http://leetcode0.blogspot.com/2016/04/334-increasing-triplet-subsequence.html
就是 逐个对比。 记录最小的两个。
    public boolean increasingTriplet(int[] nums) {
        if(nums==null || nums.length ==0)
            return false;
        int min = nums[0], secondMin = Integer.MAX_VALUE;
        for(int i =1 ;i < nums.length; i++){
            int val = nums[i];
            if(val > secondMin)
                return true;
            if(val == secondMin)
                continue;
            // now val < secondMin
            if(val<= min){
                min=val;
            }else{ //now  min < val < secondMin
                secondMin  = val;
            }
        }
        return false;
    }
http://www.1point3acres.com/bbs/thread-171521-1-1.html
不过,如果这道题改成在nums中找increasing k-subsequence,你打算怎么扩展呢?
http://yuancrackcode.com/2016/01/19/find-the-increasing-sequences-with-increasing-indices/
  1. public static int[] get(int[] nums) {
  2. if (nums == null || nums.length == 0) return new int[]{};
  3.  
  4. int n = nums.length;
  5. int[] result = new int[3], min = new int[n], max = new int[n];
  6. for (int i = 0; i < n; i++) {
  7. if (i == 0) {
  8. min[i] = nums[i];
  9. } else {
  10. min[i] = Math.min(min[i - 1], nums[i - 1]);
  11. }
  12. }
  13. for (int i = n - 1; i >= 0; i--) {
  14. if (i == n - 1) {
  15. max[i] = nums[i];
  16. } else {
  17. max[i] = Math.max(max[i + 1], nums[i + 1]);
  18. }
  19. }//find the max number after i and min number before i
  20. for (int i = 0; i < n; i++) {
  21. if (nums[i] > min[i] && nums[i] < max[i]) {
  22. result[0] = min[i];
  23. result[1] = nums[i];
  24. result[2] = max[i];
  25. break;
  26. }
  27. }
  28. return result;
  29. }
X.
http://www.cnblogs.com/grandyang/p/5194599.html
用一个dp数组,dp[i]表示在i位置之前小于等于nums[i]的数字的个数(包括其本身),我们初始化dp数组都为1,然后我们开始遍历原数组,对当前数字nums[i],我们遍历其之前的所有数字,如果之前某个数字nums[j]小于nums[i],那么我们更新dp[i] = max(dp[i], dp[j] + 1),如果此时dp[i]到3了,则返回true,若遍历完成,则返回false
    bool increasingTriplet(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                    if (dp[i] >= 3) return true;
                }
            }
        }
        return false;
    }

Read full article from [LeetCode]Increasing Triplet Subsequence | 书影博客

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts