Java O(n) solution using stack easy to understand


  • 0
    W
            if (nums == null || nums.length == 0) {
                return 0;
            }
            Stack<Integer> stack = new Stack<Integer>();
            int flag = 1;
            int res = 1;
            stack.push(nums[0]);
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] <= stack.peek() && flag == 1) {
                    stack.pop();
                    stack.push(nums[i]);
                    
                }
                else if (nums[i] >= stack.peek() && flag == -1) {
                    stack.pop();
                    stack.push(nums[i]);
                }
                else if (nums[i] > stack.peek() && flag == 1) {
                    stack.push(nums[i]);
                    flag = -1;
                    res = Math.max(res, stack.size());
                }
                else if (nums[i] < stack.peek() && flag == -1) {
                    stack.push(nums[i]);
                    flag = 1;
                    res = Math.max(res, stack.size());
                }
            }
            stack.clear();
            flag = -1;
            stack.push(nums[0]);
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] <= stack.peek() && flag == 1) {
                    stack.pop();
                    stack.push(nums[i]);
                    
                }
                else if (nums[i] >= stack.peek() && flag == -1) {
                    stack.pop();
                    stack.push(nums[i]);
                }
                else if (nums[i] > stack.peek() && flag == 1) {
                    stack.push(nums[i]);
                    flag = -1;
                    res = Math.max(res, stack.size());
                }
                else if (nums[i] < stack.peek() && flag == -1) {
                    stack.push(nums[i]);
                    flag = 1;
                    res = Math.max(res, stack.size());
                }
            }
            return res;
        }

  • 0

    @willcomeback there is a lot of redundancy in the code. If you pay attention you can reduce the code length.


  • 0
    W

    @agave you are right. This is the first draft I code I think it is much easier to follow.


Log in to reply
 

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