Thinking process + Java greedy solution O(n) time, O(1) space


  • 0
    D

    The code is at here, and the thinking process is behind it.

    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums == null || nums.length < 2) {
                return nums == null ? 0 : nums.length;
            }
            int maxLen = 1;
            int[] prev = new int[nums.length];
            for (int i = 1; i < nums.length; i++) {
                if ((i == 1 && nums[i] != nums[i - 1]) || (i > 1 && (nums[i] - nums[i - 1]) * (nums[i - 1] - prev[i - 1]) < 0)) {
                    prev[i] = nums[i - 1];
                    maxLen++;
                } else {
                    prev[i] = prev[i - 1];
                }
            }
            return maxLen;
        }
    }
    

    We can first do DP O(n^2) because this is similar with Longest Increasing Subsequence problem. However, after some thinking, I think it is hard to use the "Patience sort" O(nlogn) solution of LIS problem here. O(nlogn) isn't satisfactory here anyway.

    So I decide to optimize the O(n^2) solution. We need to choose from subproblem 1 to i - 1. If there is one subproblem that is always correct, then we will find a greedy solution, and reduce the time complexity to O(n).

    I have thought about trying the sequence that has the biggest tail number. However, I have given myself a counter-example. 1 1000 2 6 5. When we consider 5, and try to attach 5 to the sequence that has the largest tail number 1000, then it's wrong.

    So I turn to try to attach the number to the longest subsequence so far.
    Two cases. If it is valid to attach, then we have made the longest subsequence even longer; if it is not valid, then we can throw away the tail number, and attach the new number to the thrown number's previous number, and still maintain the length of longest subsequence.

    Other details: notice we only need to try to attach the new number to the longest subsequence found so far because it's meaningless to attach the new number to some shorter subsequence. So this means the dp[i] is a non-decreasing function.

    Further space optimization:

    Since prev[] array is only used for i-1 number. We can reduce space complexity.

    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums == null || nums.length < 2) {
                return nums == null ? 0 : nums.length;
            }
            int maxLen = 1;
            int prev = 0;
            for (int i = 1; i < nums.length; i++) {
                if ((i == 1 && nums[i] != nums[i - 1]) || (i > 1 && (nums[i] - nums[i - 1]) * (nums[i - 1] - prev) < 0)) {
                    prev = nums[i - 1];
                    maxLen++;
                } 
            }
            return maxLen;
        }
    }
    

Log in to reply
 

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