[LeetCode] 896. Monotonic Array 单调数组
2023-09-11 14:21:37 时间
An array is *monotonic* if it is either monotone increasing or monotone decreasing.
An array A
is monotone increasing if for all i <= j
, A[i] <= A[j]
. An array A
is monotone decreasing if for all i <= j
, A[i] >= A[j]
.
Return true
if and only if the given array A
is monotonic.
Example 1:
Input: [1,2,2,3]
Output: true
Example 2:
Input: [6,5,4,4]
Output: true
Example 3:
Input: [1,3,2]
Output: false
Example 4:
Input: [1,2,4,5]
Output: true
Example 5:
Input: [1,1,1]
Output: true
Note:
1 <= A.length <= 50000
-100000 <= A[i] <= 100000
这道题让我们判断一个数组是否单调,单调数组就是说这个数组的数字要么是递增的,要么是递减的,不存在一会儿递增一会儿递减的情况,即不会有山峰存在。这里不是严格的递增或递减,是允许有相同的数字的。那么我们直接将相邻的两个数字比较一下即可,使用两个标识符,inc 和 dec,初始化均为 true,我们开始时假设这个数组既是递增的又是递减的,当然这是不可能的,我们会在后面对其进行更新。在遍历数组的时候,只要发现某个数字大于其身后的数字了,那么 inc 就会赋值为 false,同理,只要某个数字小于其身后的数字了,dec 就会被赋值为 false,所以在既有递增又有递减的数组中,inc 和 dec 都会变为 false,而在单调数组中二者之间至少有一个还会保持为 true,参见代码如下:
解法一:
class Solution {
public:
bool isMonotonic(vector<int>& A) {
bool inc = true, dec = true;
for (int i = 1; i < A.size(); ++i) {
inc &= (A[i - 1] <= A[i]);
dec &= (A[i - 1] >= A[i]);
if (!inc && !dec) return false;
}
return true;
}
};
跟上面的解法思路很像,只不过没有用 bool 型的,而是用了整型数字来记录递增和递减的个数,若是单调数组,那么最终在 inc 和 dec 中一定会有一个值是等于数组长度的,参见代码如下:
解法二:
class Solution {
public:
bool isMonotonic(vector<int>& A) {
int inc = 1, dec = 1, n = A.size();
for (int i = 1; i < n; ++i) {
inc += (A[i - 1] <= A[i]);
dec += (A[i - 1] >= A[i]);
}
return (inc == n) || (dec == n);
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/896
参考资料:
https://leetcode.com/problems/monotonic-array/
https://leetcode.com/problems/monotonic-array/discuss/165889/C%2B%2BJavaPython-One-Pass-O(N)
https://leetcode.com/problems/monotonic-array/discuss/172578/Java-O(n)-simple-solution
[LeetCode All in One 题目讲解汇总(持续更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)
相关文章
- 【LeetCode-面试算法经典-Java实现】【033-Search in Rotated Sorted Array(在旋转数组中搜索)】
- LeetCode高频题88. 合并两个有序数组
- 169、【动态规划】leetcode ——123. 买卖股票的最佳时机 III:二维数组+一维数组 (C++版本)
- 159、【动态规划】leetcode ——322. 零钱兑换:二维数组+一维滚动数组(C++版本)
- 【leetcode】26:删除有序数组中的重复项 II
- [LeetCode] 1331. Rank Transform of an Array 数组序号转换
- [LeetCode] 1250. Check If It Is a Good Array 检查好数组
- [LeetCode] 1013. Partition Array Into Three Parts With Equal Sum 将数组分成和相等的三个部分
- [LeetCode] 978. Longest Turbulent Subarray 最长湍流子数组
- [LeetCode] 954. Array of Doubled Pairs 两倍数对儿数组
- [LeetCode] 915. Partition Array into Disjoint Intervals 分割数组为不相交的区间
- [LeetCode] Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和
- [LeetCode] 713. Subarray Product Less Than K 子数组乘积小于K
- [LeetCode] 457. Circular Array Loop 环形数组循环
- [LeetCode] Split Array with Equal Sum 分割数组成和相同的子数组
- [LeetCode] Array Partition I 数组分割之一
- [LeetCode] 532. K-diff Pairs in an Array 数组中差为K的数对
- [LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串
- [LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和
- [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项
- leetcode 697. Degree of an Array 数组的度(简单)
- leetcode 540. Single Element in a Sorted Array 有序数组中的单一元素
- leetcode 81. Search in Rotated Sorted Array II 搜索旋转排序数组 II(中等)