69精品人人人人人人人人人,七里香社区在线看,狠狠色婷婷久久综合频道日韩,4949澳门今晚开奖结果

解法一：采用遞歸方式，簡潔明了，但效率很低，存在大量的重復計算。

f(10)
/        \
f(9)         f(8)
/     \       /    \
f(8)     f(7)  f(7)   f(6)
/   \     /   \
f(7)  f(6)  f(6) f(5)

解法二：從下往上計算，遞推，時間復雜度 `O(n)`。

無

A

無

A

無

B

無

枚舉法;D

無

A

無

方法一：排序

思路與算法

對于每一個形如 A[i] = v 的元素，我們將其索引 i 按照對應值 v 排序之后的順序寫下。例如， A[0] = 7, A[1] = 2, A[2] = 5, A[3] = 4，我們應該這樣順序寫下索引值 i=1, i=3, i=2, i=0。

然后，當我們寫下一個索引 i 的時候，我們可以得到候選的寬度答案 i - min(indexes_previously_written) （如果這個值是正數的話）。 我們可以用一個變量 m 記錄已經寫下的最小索引。

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

復雜度分析

• 時間復雜度： $O(N \log N)$，其中 $N$ 是 A 的長度。

• 空間復雜度： $O(N)$，基于排序的實現方法。

---

方法二：二分檢索候選位置

思路

按照降序考慮 i ， 我們希望找到一個最大的 j 滿足 A[j] >= A[i]（如果存在的話）。

因此，候選的 j 應該是降序的：如果存在 j1 < j2 并且 A[j1] <= A[j2] ，那么我們一定會選擇 j2。

算法

我們使用列表記錄這些候選的 j。舉一個例子，當 A = [0,8,2,7,5]，對于 i = 0 的候選列表應該是 candidates = [(v=5, j=4), (v=7, j=3), (v=8, j=1)]。我們要時刻維護候選列表 candidates 按照索引值降序，對應值升序。

現在，我們可以使用二分檢索的辦法找到最大的索引 j 滿足 A[j] >= A[i]：也就是列表中第一個滿足 v >= A[i] 的那一項。

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

復雜度分析

• 時間復雜度： $O(N \log N)?$，其中 $N?$ 是數組 A 的長度。

• 空間復雜度： $O(N)$。

無

方法一：暴力法

預訂新的日程安排 [start, end) 時，檢查當前每個日程安排是否與新日程安排沖突。若不沖突，則可以添加新的日程安排。

算法： 我們將維護一個日程安排列表（不一定要排序）。當且僅當其中一個日程安排在另一個日程安排結束后開始時，兩個日程安排 [s1，e1) 和 [s2，e2) 不沖突：e1<=s2 或 e2<=s1。這意味著當 s1<e2 和 s2<e1 時，日程安排發生沖突。

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;
    }
}

復雜度分析

• 時間復雜度：$O(N^2)$。$N$ 指的是日常安排的數量，對于每個新的日常安排，我們檢查新的日常安排是否發生沖突來決定是否可以預訂新的日常安排。所以時間復雜度為 $\sum_k^N O(k) = O(N^2)$。
• 空間復雜度：$O(n)$，calendar 所使用的空間大小。

方法二：平衡樹

如果我們按時間順序維護日程安排，則可以通過二分查找日程安排的情況來檢查新日常安排是否可以預訂，時間復雜度為 $O(\log N)$ （其中 $N$ 是已預訂的日常安排數），若可以預定則我們還需要在排序結構中插入日常安排。

算法： - 我們需要一個數據結構能夠保持元素排序和支持快速插入。在 java 中，TreeMap 是最適合的。在 python 中，我們可以構建自己的二叉樹結構。

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;
    }
}

復雜度分析

• 時間復雜度 (Java)：$O(N \log N)$。其中 $N$ 是預訂的日程安排數。對于每個新日程安排，我們用 $O(\log N)$ 的時間搜索該日程安排是否合法，若合法則將其插入日常安排中需要 $O(1)$ 的時間。
• 時間復雜度 (Python)：最壞的情況 $O(N^2)$，其他情況是 $O(N \log N)$。對于每個新日程安排，若新日程安排合法則將新日程安排插入到二叉樹中。由于此樹可能不平衡，因此可能需要線性步驟來遍歷每個日常安排。
• 空間復雜度：$O(N)$，數據結構所使用的空間。

無

跳上 `n` 級臺階，可以從 `n-1` 級跳 `1` 級上去，也可以從 `n-2` 級跳 `2` 級上去。所以f(n) = f(n-1) + f(n-2)

無

C

無