这是悦乐书的第 345 次更新, 第 369 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 210 题 (顺位题号是 896). 如果数组单调递增或单调递减, 则数组是单调的. 如果对于所有 i <= j,A[i] <= A[j], 则数组 A 是单调递增的. 如果对于所有 i <= j,A[i]>= A[j], 则数组 A 是单调递减的. 当且仅当给定的数组 A 是单调的时, 才返回 true. 例如:
输入:[1,2,2,3]
输出: true
输入:[6,5,4,4]
输出: true
输入:[1,3,2]
输出: false
输入:[1,2,4,5]
输出: true
输入:[1,1,1]
输出: true
注意:
- 1 <= A.length <= 50000
- -100000 <= A [i] <= 100000
02 第一种解法
使用两个循环, 一个判断是否递增, 一个判断是否递减, 只要其中一个符合条件即可返回 true.
- public boolean isMonotonic(int[] A) {
- return isIncrease(A) || isDecrease(A);
- }
- public boolean isIncrease(int[] A) {
- for (int i=0; i<A.length-1; i++) {
- if (A[i]> A[i+1]) {
- return false;
- }
- }
- return true;
- }
- public boolean isDecrease(int[] A) {
- for (int i=0; i<A.length-1; i++) {
- if (A[i] <A[i+1]) {
- return false;
- }
- }
- return true;
- }
03 第二种解法
也可以只是用一次循环.
- public boolean isMonotonic2(int[] A) {
- boolean isincrease = true;
- boolean isdecrease = true;
- int n = A.length;
- for (int i=0; i<n-1; i++) {
- isincrease = isincrease && A[i] <= A[i+1];
- isdecrease = isdecrease && A[i]>= A[i+1];
- }
- return isincrease || isdecrease;
- }
04 第三种解法
针对第二种解法, 我们分两种情况分别处理了 isincrease,isdecrease 两个变量.
- public boolean isMonotonic3(int[] A) {
- boolean isincrease = true;
- boolean isdecrease = true;
- int n = A.length;
- for (int i=0; i<n-1; i++) {
- if (A[i] <A[i+1]) {
- isdecrease = false;
- }
- if (A[i]> A[i+1]) {
- isincrease = false;
- }
- }
- return isincrease || isdecrease;
- }
05 第四种解法
也可以借助包装类 Integer 的 compare 方法, 比较相邻两个元素的大小, 另外使用一个变量存储上一次比较的结果, 每次做完新的比较后, 用新的结果和前一次的结果比较, 只要前后两次比较结果不同, 可以直接返回 false.
- public boolean isMonotonic4(int[] A) {
- int flag = 0, n = A.length;
- for (int i=0; i<n-1; i++) {
- int num = Integer.compare(A[i], A[i+1]);
- if (num != 0) {
- if (flag != 0 && flag != num) {
- return false;
- }
- flag = num;
- }
- }
- return true;
- }
06 小结
算法专题目前已连续日更超过六个月, 算法题文章 213 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/2a6ebb06c73b