Skip to content

2863. Maximum Length of Semi-Decreasing Subarrays 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int maxSubarrayLength(vector<int>& nums) {
    int ans = 0;
    stack<int> stack;

    for (int i = nums.size() - 1; i >= 0; --i)
      // If nums[stack.top()] <= nums[i], stack.top() is better than i.
      // So, no need to push it.
      if (stack.empty() || nums[stack.top()] > nums[i])
        stack.push(i);

    for (int i = 0; i < nums.size(); ++i)
      while (!stack.empty() && num > nums[stack.top()])
        ans = max(ans, stack.top() - i + 1), stack.pop();

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int maxSubarrayLength(int[] nums) {
    int ans = 0;
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = nums.length - 1; i >= 0; --i)
      // If nums[stack.peek()] <= nums[i], stack.peek() is better than i.
      // So, no need to push it.
      if (stack.isEmpty() || nums[stack.peek()] > nums[i])
        stack.push(i);

    for (int i = 0; i < nums.length; ++i)
      while (!stack.isEmpty() && nums[i] > nums[stack.peek()])
        ans = Math.max(ans, stack.pop() - i + 1);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxSubarrayLength(self, nums: list[int]) -> int:
    ans = 0
    stack = []

    for i in range(len(nums) - 1, -1, -1):
      # If nums[stack[-1]] <= nums[i], stack[-1] is better than i.
      # So, no need to append it.
      if not stack or nums[stack[-1]] > nums[i]:
        stack.append(i)

    for i, num in enumerate(nums):
      while stack and num > nums[stack[-1]]:
        ans = max(ans, stack.pop() - i + 1)

    return ans