手機(jī)預(yù)覽
復(fù)制鏈接
新浪微博
分享QQ
微信掃一掃
解法一：采用遞歸方式，簡(jiǎn)潔明了，但效率很低，存在大量的重復(fù)計(jì)算。
f(10)
/ \
f(9) f(8)
/ \ / \
f(8) f(7) f(7) f(6)
/ \ / \
f(7) f(6) f(6) f(5)
解法二：從下往上計(jì)算，遞推，時(shí)間復(fù)雜度 `O(n)`。
方法一：排序
思路與算法
對(duì)于每一個(gè)形如 A[i] = v 的元素，我們將其索引 i 按照對(duì)應(yīng)值 v 排序之后的順序?qū)懴?。例如?A[0] = 7, A[1] = 2, A[2] = 5, A[3] = 4，我們應(yīng)該這樣順序?qū)懴滤饕?i=1, i=3, i=2, i=0。
然后，當(dāng)我們寫下一個(gè)索引 i 的時(shí)候，我們可以得到候選的寬度答案 i - min(indexes_previously_written) （如果這個(gè)值是正數(shù)的話）。 我們可以用一個(gè)變量 m 記錄已經(jīng)寫下的最小索引。
class Solution {
public int maxWidthRamp(int[] A) {
int N = A.length;
Integer[] B = new Integer[N];
for (int i = 0; i < N; ++i)
B[i] = i;
Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));
int ans = 0;
int m = N;
for (int i: B) {
ans = Math.max(ans, i - m);
m = Math.min(m, i);
}
return ans;
}
}
class Solution(object):
def maxWidthRamp(self, A):
ans = 0
m = float('inf')
for i in sorted(range(len(A)), key = A.__getitem__):
ans = max(ans, i - m)
m = min(m, i)
return ans
復(fù)雜度分析
-
時(shí)間復(fù)雜度： $O(N \log N)$，其中 $N$ 是
A的長(zhǎng)度。 -
空間復(fù)雜度： $O(N)$，基于排序的實(shí)現(xiàn)方法。
方法二：二分檢索候選位置
思路
按照降序考慮 i ， 我們希望找到一個(gè)最大的 j 滿足 A[j] >= A[i]（如果存在的話）。
因此，候選的 j 應(yīng)該是降序的：如果存在 j1 < j2 并且 A[j1] <= A[j2] ，那么我們一定會(huì)選擇 j2。
算法
我們使用列表記錄這些候選的 j。舉一個(gè)例子，當(dāng) A = [0,8,2,7,5]，對(duì)于 i = 0 的候選列表應(yīng)該是 candidates = [(v=5, j=4), (v=7, j=3), (v=8, j=1)]。我們要時(shí)刻維護(hù)候選列表 candidates 按照索引值降序，對(duì)應(yīng)值升序。
現(xiàn)在，我們可以使用二分檢索的辦法找到最大的索引 j 滿足 A[j] >= A[i]：也就是列表中第一個(gè)滿足 v >= A[i] 的那一項(xiàng)。
import java.awt.Point;
class Solution {
public int maxWidthRamp(int[] A) {
int N = A.length;
int ans = 0;
List<Point> candidates = new ArrayList();
candidates.add(new Point(A[N-1], N-1));
// candidates: i's decreasing, by increasing value of A[i]
for (int i = N-2; i >= 0; --i) {
// Find largest j in candidates with A[j] >= A[i]
int lo = 0, hi = candidates.size();
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (candidates.get(mi).x < A[i])
lo = mi + 1;
else
hi = mi;
}
if (lo < candidates.size()) {
int j = candidates.get(lo).y;
ans = Math.max(ans, j - i);
} else {
candidates.add(new Point(A[i], i));
}
}
return ans;
}
}
class Solution(object):
def maxWidthRamp(self, A):
N = len(A)
ans = 0
candidates = [(A[N-1], N-1)]
# candidates: i's decreasing, by increasing value of A[i]
for i in xrange(N-2, -1, -1):
# Find largest j in candidates with A[j] >= A[i]
jx = bisect.bisect(candidates, (A[i],))
if jx < len(candidates):
ans = max(ans, candidates[jx][1] - i)
else:
candidates.append((A[i], i))
return ans
復(fù)雜度分析
-
時(shí)間復(fù)雜度： $O(N \log N)?$，其中 $N?$ 是數(shù)組
A的長(zhǎng)度。 -
空間復(fù)雜度： $O(N)$。
方法一：暴力法
預(yù)訂新的日程安排 [start, end) 時(shí)，檢查當(dāng)前每個(gè)日程安排是否與新日程安排沖突。若不沖突，則可以添加新的日程安排。
算法： 我們將維護(hù)一個(gè)日程安排列表（不一定要排序）。當(dāng)且僅當(dāng)其中一個(gè)日程安排在另一個(gè)日程安排結(jié)束后開始時(shí)，兩個(gè)日程安排 [s1，e1) 和 [s2，e2) 不沖突：e1<=s2 或 e2<=s1。這意味著當(dāng) s1<e2 和 s2<e1 時(shí)，日程安排發(fā)生沖突。
class MyCalendar(object):
def __init__(self):
self.calendar = []
def book(self, start, end):
for s, e in self.calendar:
if s < end and start < e:
return False
self.calendar.append((start, end))
return True
public class MyCalendar {
List<int[]> calendar;
MyCalendar() {
calendar = new ArrayList();
}
public boolean book(int start, int end) {
for (int[] iv: calendar) {
if (iv[0] < end && start < iv[1]) return false;
}
calendar.add(new int[]{start, end});
return true;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：$O(N^2)$。$N$ 指的是日常安排的數(shù)量，對(duì)于每個(gè)新的日常安排，我們檢查新的日常安排是否發(fā)生沖突來(lái)決定是否可以預(yù)訂新的日常安排。所以時(shí)間復(fù)雜度為 $\sum_k^N O(k) = O(N^2)$。
- 空間復(fù)雜度：$O(n)$，
calendar所使用的空間大小。
方法二：平衡樹
如果我們按時(shí)間順序維護(hù)日程安排，則可以通過二分查找日程安排的情況來(lái)檢查新日常安排是否可以預(yù)訂，時(shí)間復(fù)雜度為 $O(\log N)$ （其中 $N$ 是已預(yù)訂的日常安排數(shù)），若可以預(yù)定則我們還需要在排序結(jié)構(gòu)中插入日常安排。
算法： - 我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)能夠保持元素排序和支持快速插入。在 java 中，TreeMap 是最適合的。在 python 中，我們可以構(gòu)建自己的二叉樹結(jié)構(gòu)。
class Node:
__slots__ = 'start', 'end', 'left', 'right'
def __init__(self, start, end):
self.start = start
self.end = end
self.left = self.right = None
def insert(self, node):
if node.start >= self.end:
if not self.right:
self.right = node
return True
return self.right.insert(node)
elif node.end <= self.start:
if not self.left:
self.left = node
return True
return self.left.insert(node)
else:
return False
class MyCalendar(object):
def __init__(self):
self.root = None
def book(self, start, end):
if self.root is None:
self.root = Node(start, end)
return True
return self.root.insert(Node(start, end))
class MyCalendar {
TreeMap<Integer, Integer> calendar;
MyCalendar() {
calendar = new TreeMap();
}
public boolean book(int start, int end) {
Integer prev = calendar.floorKey(start),
next = calendar.ceilingKey(start);
if ((prev == null || calendar.get(prev) <= start) &&
(next == null || end <= next)) {
calendar.put(start, end);
return true;
}
return false;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度 (Java)：$O(N \log N)$。其中 $N$ 是預(yù)訂的日程安排數(shù)。對(duì)于每個(gè)新日程安排，我們用 $O(\log N)$ 的時(shí)間搜索該日程安排是否合法，若合法則將其插入日常安排中需要 $O(1)$ 的時(shí)間。
- 時(shí)間復(fù)雜度 (Python)：最壞的情況 $O(N^2)$，其他情況是 $O(N \log N)$。對(duì)于每個(gè)新日程安排，若新日程安排合法則將新日程安排插入到二叉樹中。由于此樹可能不平衡，因此可能需要線性步驟來(lái)遍歷每個(gè)日常安排。
- 空間復(fù)雜度：$O(N)$，數(shù)據(jù)結(jié)構(gòu)所使用的空間。
跳上 `n` 級(jí)臺(tái)階，可以從 `n-1` 級(jí)跳 `1` 級(jí)上去，也可以從 `n-2` 級(jí)跳 `2` 級(jí)上去。所以f(n) = f(n-1) + f(n-2)
