为什么这个需要 20 天才能结束，感觉 14 天足够了啊，只是想做点中等题。

第一天，两个简单题试试水~

896. Monotonic Array

Analysis

题意是判断给定的数组是不是单调的，感觉比较简单，一个循环就搞定了。

Code

method 1

因为要确定数组是递减的还是递增的，所以对前两个出现的不相等元素进行比较。所以这里就有一个坑，不能直接那数组的第一个元素跟第二个元素进行比较。

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        int size = nums.size();
        if(size == 1) return true;
        int p1 = 0, p2 = 1;
        while(p1 < size && p2 < size && nums[p1] == nums[p2]) p1++, p2++;
        if(p2 == size) return true;
        if(nums[p1] >= nums[p2]) {
            for(int i = p1; i < size - 1; i++) {
                if(nums[i] < nums[i + 1]) return false;
            }
        } else {
            for(int i = p1; i < size - 1; i++) {
                if(nums[i] > nums[i + 1]) return false;
            }
        }
        return true;
    }
};

注意这种方法只用遍历一次数组，时间复杂度为 $O(n)$。
实际上，可以精简一下这种思考模式。
对于一个数组而言，其内部相邻的元素可能存在 3 种关系：相等、大于和小于。按照题目的要求，单调的数组只存在两种情况：

相邻元素大于等于
相邻元素小于等于

并且这两种情况只可能出现一种，如果两种同时出现，那这个数组一定不是单调的。此时，问题就转化判断数组内相邻元素的情况了，那么就可以这样写了：

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        bool inc = true, dec = true;
        int size = nums.size();
        for(int i = 0; i < size - 1; i++) {
            if(nums[i] > nums[i + 1]) inc = false;
            if(nums[i] < nums[i + 1]) dec = false;
        }
        return inc || dec;
    }
};

method 2

实际上，判断单调就是判断数组是否有序，那就可以直接接用现成的库函数。

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        return is_sorted(nums.begin(), nums.end()) || is_sorted(nums.rbegin(), nums.rend());
    }
};

注意这样需要遍历 2 次数组，但时间复杂度依然是 $O(n)$。

28. Implement strStr()

Analysis

题意很直接，实现 strstr 函数即可。
话说，这个查找子串的题让我想到了 KMP...
不过，这是道 easy 题。如果目的是锻炼一下 KMP 的话，估计是 hard 了。
日后复习 KMP 的时候再补一下这个题吧。

Code

method 1

先暴力做一下：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int pos = -1, len1 = haystack.length(), len2 = needle.length();
        if(len2 == 0) return 0;
        for(int i = 0; i < len1; i++) {
            if(haystack[i] == needle[0]) {
                int tmp = i + 1, j;
                for(j = 1; j < len2; j++, tmp++) {
                    if(needle[j] != haystack[tmp]) break;
                }
                if(j == len2) {
                    pos = i;
                    break;
                }
            } 
        }
        return pos;
    }
};

注意别丢了 needle 为空串的情况。

method 2

复习一下 string 容器的库函数😂：

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

Summary

总共 20 天，41 个题，一天才 2 个题，为什么不设置成 14 天，一天 2 - 3 个题呢？
虽说是基础，一天 3 个中等题应该是也可以接受的吧？