O(n) DP and Stack Solution


  • 0

    DP with array

    public int wiggleMaxLength(int[] nums) {
            if(nums.length==0) return 0;
            int[] up = new int[nums.length];
            int[] down = new int[nums.length];
            Arrays.fill(up,1);
            Arrays.fill(down,1);
            for(int i=1;i<nums.length;i++) {
                if(nums[i]>nums[i-1]) up[i] = Math.max(down[i-1] + 1,up[i-1]);
                if(nums[i]<nums[i-1]) down[i] =Math.max(up[i-1] + 1,down[i-1]);
                if(nums[i]==nums[i-1]) {
                    up[i] = up[i-1];
                    down[i] = down[i-1];
                }
            }
            return Math.max(up[nums.length-1],down[nums.length-1]);
        }
    

    DP without array (since we just used the previous number in the array)

    public int wiggleMaxLength(int[] nums) {
            if(nums.length==0) return 0;
            int up = 1;
            int down = 1;
            for(int i=1;i<nums.length;i++) {
                if(nums[i]>nums[i-1]) up = Math.max(down + 1,up);
                if(nums[i]<nums[i-1]) down =Math.max(up + 1,down);
            }
            return Math.max(up,down);
        }
    

    stack:

    public int wiggleMaxLength(int[] nums) {
            if(nums.length==0) return 0;
            Stack<Integer> st = new Stack<>();
            int up = 1;
            int prev = 0;
            int ans = 1;
            st.push(nums[0]);
            for(int i = 1;i<nums.length;i++) {
                up = 0;
                while(!st.isEmpty()&&st.peek()>nums[i]) {
                    st.pop();
                    up = 2;
                }
                if(up==0){
                    if(st.isEmpty()||st.peek()<nums[i]) up = 1;
                }
                 if((up==1||up==2)&&prev!=up) {
                    ans++;
                    prev = up;
                }
                st.push(nums[i]);
            }
            return ans;
        }
    

    int up: 0 - the same with the peek of stack
    1 - larger than the peek of stack
    2 - smaller than the peek of stack
    int prev: the previous up value;

    if you visualize the number trend (1,7,4,5,5), you can see something like: 
             _
    /  \  /      
    or (1,7,4,9,2,5)
    
    / \ / \ / \
    
    

    the basic idea is quite like dp solution, if number goes up (/), find the longest length of the sequence that is end with number going down. if number goes down (\), find the longest length of the sequence that is end with number going up. ignore the same adjacent value (-).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.