猩猩的乐园

原题说明

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3is a peak element and your function should return the index number 2.

Note:

Your solution should be in logarithmic complexity.

解题思路

题目要求给出一个数列中峰值的位置。注意的是数列中可能存在若干个峰值，我们只要给出其中任意一个的位置即可。举个例子：数列 [0,0,0,4,0,0,5,0,0]， 它的峰值分别是4,5，因此答案应该是3或者6。

最直接的想法用暴力搜索，直接遍历一遍数组，给出最大值得位置即可。这样时间复杂度是 O(n)。

如果我们想要降低时间复杂度到O(log n)，直觉上可以用二分搜索（Binary Search）。若是只有一个峰值，设最左边位置为low，最右边位置为high，这样中间位置为 mid = (high + low) / 2。判断准则为，若是 num[mid] < num[mid+1], 我们就让low = mid，反之high = mid， 直到 low + 1等于high,终止二分。

有趣的是，如果存在若干个峰值，我们也不需要对以上算法进行改动。因为进过若干次的二分，在位置low和high之间终归会存在一个且仅有一个峰值。

示例代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low, high = 0, len(nums) - 1
        while low < high:
            mid = int(low + (high - low) / 2)
            if nums[mid] > nums[mid + 1]:
                high = mid
            else:
                low = mid + 1
        return low

示例代码 (c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int findPeakElement(const vector<int>& nums) {
        int low = 0; 
        int high = nums.size() - 1;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < nums[mid + 1]) 
                low = mid;
            else
                high = mid;
        }
        return nums[low] > nums[high] ? low : high;
    }
};

复杂度分析

典型的二分法算法，并且只需要 low, high, mid 3个变量，所以时间和空间复杂度分别为：

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

总结归纳：

这是一道经典的二分算法题（Binary Search），一般如果要求在对数时间复杂度下完成，我们可以考虑使用二分搜索。今天的解题就到这里了，种香蕉树去了：）

原题说明

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

解题步骤

这又是一道可以用Stack来解决的问题。

1. 建立降序栈stk,存temperatures数组对应的 index
2. 建立返回数组rets并且初始化为0
3. 遍历temperatures数组：
   • 每一个元素temp和stk的栈顶元素对应值比较，如果temp较大，说明遇到了 warmer temperature，所以在rets中更新栈顶元素对应的值，并且 pop 栈顶元素
   • 重复上述过程，直到stk为空或者temp比栈顶值小，将当前index 进栈

示例代码(CPP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        // 注意需要初始化为0
        vector<int> rets(n, 0);
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                rets[stk.top()] = i - stk.top();
                stk.pop();
            }
            // 注意push的是index，不是值
            stk.push(i);
        }
        return rets;
    }
};

示例代码(PYTHON)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        # 使用List代替stack
        stack = list()
        res = [0 for  i in range(len(temperatures))]
        for i in range(len(temperatures)):
            while(len(stack) > 0 and temperatures[i] > temperatures[stack[-1]]):
                res[stack[-1]] = i - stack[-1];
                stack.pop()
            # append等效为stack中的push
            stack.append(i)
        return res

复杂度分析

因为每个字符push和pop都是最多一次，所以：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

总结归纳：

运用Stack的题目很多，这类问题的做法是遍历输入数组，当前元素与栈顶元素比较，如果当前元素更优（不同题目条件不同，比如本题对应当前元素较大）则pop栈顶元素，直到栈顶元素更优为止，而后插入当前元素。

类似的题目还有：
[LeetCode 316] Remove Duplicate Letters 移除重复字母

最近会总结更多这类题目更新在Stack Tag中，尽请期待，吃香蕉去了：）

原题说明

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

解题步骤

1. 建立哈希表（或者数组)mapping来统计字符串中每一个字母出现的频率
2. 建立哈希表（或者数组)visited来记录已经插入ret (return string) 的字母
3. 将 ret 当作 stack，用 Greedy (贪心法）遍历字符串 s ：
   • 若当前字符已经在 visited 中了，直接 continue
   • 当前字符 ch 与 ret 字符串的末尾元素（栈顶）比较，若 ch 靠前，并且 mapping 中栈顶元素大于0 (即之后遍历中还会出现栈顶元素)，则 pop ret末尾元素，如此反复，直到 ret 末尾元素靠前，或者 ret 为空
   • 在 ret 中插入当前字符 ch
   • 插入与 pop 过程都不要忘记更新 visited

示例代码(CPP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> mapping;
        unordered_set<char> visited;
        for (auto& ch : s) {
            mapping[ch]++;
        }
        string ret;
        for (auto& ch : s) {
            mapping[ch]--;
            if (visited.count(ch)) {
                continue;
            }
            while (ret.size() && ret.back() > ch && mapping[ret.back()] > 0) {
                visited.erase(ret.back());
                ret.pop_back();
            }
            ret += ch;
            visited.insert(ch);
        }
        return ret;
    }
};

示例代码(PYTHON)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from collections import Counter
class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        map = Counter()
        stack = list()
        visited = set()
        for c in s:
            map[c] += 1
        for c in s:
            map[c] -= 1;
            if c in visited: continue
            else: visited.add(c)
            while(len(stack) > 0 and c < stack[-1] and map[stack[-1]] > 0):
                visited.remove(stack[-1])
                stack.pop()
            stack.append(c)
            visited.add(c)
        return ''.join(stack)

复杂度分析

因为每个字符插入和pop出ret都是最多一次，所以：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

总结归纳：

运用Stack加贪心法的题目有很多，这类问题的做法是遍历输入数组，当前元素与栈顶元素比较，如果当前元素更优（不同题目条件不同，比如本题对应当前元素较小）则pop栈顶元素，直到栈顶元素更优为止，而后插入当前元素。

最近会着重介绍这类题目，之后会将链接贴在这里，尽请期待，吃香蕉去了：）