Monotonic Array
A monotonic array is one that is either entirely non-increasing or non-decreasing. That is, the elements either always increase or always decrease.
For example:
[1, 2, 4, 6, 8] is monotonic increasing [8, 6, 4, 2, 1] is monotonic decreasing
Java example to check if monotonic:
|
|
C++ example:
|
|
Python example:
|
|
Monotonicity allows optimizing certain array algorithms. Useful for bounding and binary search.
To determine if an array is monotonic (either increasing or decreasing), we can simply iterate through the array and track the increasing and decreasing trends.
Approach:
- Initialize Variables: Create two variables
increasing
anddecreasing
and set them toTrue
. - Iterate Through the Array: Loop through the array from index
1
tolen(nums) - 1
. - Check Monotonicity: Compare
nums[i]
withnums[i-1]
:- If
nums[i] < nums[i-1]
, setincreasing
toFalse
. - If
nums[i] > nums[i-1]
, setdecreasing
toFalse
.
- If
- Final Check: If either
increasing
ordecreasing
isTrue
, returnTrue
. Otherwise, returnFalse
.
Code:
|
|
Example:
- Input:
nums = [1,2,2,3]
- Output:
true
- Explanation: The array is monotone increasing since every element is less than or equal to the next element.
Insights:
- Time Complexity: The time complexity is (O(n)), where (n) is the length of the array.
- Space Complexity: The space complexity is (O(1)) since we are using only a constant amount of space.
- One-Pass Algorithm: This solution efficiently checks both monotonic increasing and decreasing trends in a single pass through the array.
|
|