花花酱 Amortized Analysis 均摊分析 SP7

By zxi on September 17, 2018

Amortized Analysis

Amortized analysis can help us understand the actual cost of n operations on a data structure. Since some operations can be really fast e.g. O(1), but some operations can be really slow e.g. O(n). We could say the time complexity of that operation is O(n). However, it does not reflect the actual performance. And turns out, we can prove that certain operations have an amortized cost of O(1) while they can take O(n) in the worst case.

均摊分析可以帮助我们了解对一个数据结构进行n次操作的真实代价。对于相同的操作，有时候可以非常快，例如在O(1)时间内完成，而有时候则需要O(n)。我们当然可以说这个操作最坏情况下的时间复杂度是O(n)，但是这并不能真实反映它的实际复杂度。通过均摊分析，我们可以证明，尽管有些操作在最坏情况下是O(n)的时间复杂度，但是均摊下来只需要O(1)。

Dynamic Array

dynamic array doubles its size when it’s full which could take O(i) time where i is the number of elements in the array. Otherwise just store the element which only cost O(1). We can use aggregate method to compute the amortized cost of dynamic array.

动态数组在容量满时将容量翻翻，这一步需要O(i)时间，i是当前数组中的元素个数。如果没有满，只需要将元素存储下来即可，只需要花费O(1)时间。我们可以使用聚合法来计算均摊成本。

((1 + 1) + (1 + 2) + (1) + (1 + 4) + (1) + (1) + (1) + (1+8) + … + (1+n)) / n, assuming n is 2^k.

= (1 * n + (1 + 2 + 4 + 8 + … + n)) / n = (n + 2n – 1) / n = 3. O(1)

C++

#include <iostream>

#include <algorithm>

using namespace std;

class DynamicArray {

public:

DynamicArray() {

data_ = new int[1];

capcity_ = 1;

}

void add(int x) {

data_[size_++] = x;

++total_cost_;

if (size_ == capcity_) {

capcity_ *= 2;

total_cost_ += size_;

int* new_data = new int[capcity_];

copy(data_, data_ + size_, new_data);

swap(new_data, data_);

delete [] new_data;

}

int totalCost() const { return total_cost_; }

private:

int total_cost_ = 0;

int size_ = 0;

int capcity_;

int* data_;

};

int main() {

DynamicArray arr;

for (int i = 1; i <= 16; ++i) {

arr.add(i);

cout <(i) << endl;

}

Output

1 average cost: 2

2 average cost: 2.5

3 average cost: 2

4 average cost: 2.75

5 average cost: 2.4

6 average cost: 2.16667

7 average cost: 2

8 average cost: 2.875

9 average cost: 2.66667

10 average cost: 2.5

11 average cost: 2.36364

12 average cost: 2.25

13 average cost: 2.15385

14 average cost: 2.07143

15 average cost: 2

16 average cost: 2.9375

[Finished in 0.4s]

Monotonic Stack

例子2: 单调栈

往单调栈push一个元素的时候，会删除上所有小于等于它的元素。这步操作在最优情况下是O(1)时间，如果它比栈顶元素要小。在最坏情况下是O(i)时间，栈上有i个元素，它比这i个元素都要大，所以一共要pop i次。

聚合法：

由于每个元素都会被push到栈上去1次，最多会被pop1次，所以总的操作数 <= 2n。 2n / n = 2 O(1)。

会计法：

每次push之前先存k块钱，k=2, 一块钱用于push自己，一块钱留着用于pop自己。

push的时候扣除1块钱，pop的时候再扣除1块钱。但不管怎样，我的账户上的钱永远>=0。这样我们可以说push的均摊成本是k=2。同样是O(1)，尽管它的worst case是O(n)。

C++

#include <iostream>

#include <algorithm>

#include <stack>

using namespace std;

class MonotonicStack {

public:

void push(int x) {

while (!data_.empty() && x > data_.top()) {

this->pop();

}

++total_cost_;

data_.push(x);

}

int pop() {

++total_cost_;

int t = data_.top();

data_.pop();

return t;

}

int totalCost() const { return total_cost_; }

private:

int total_cost_ = 0;

stack<int> data_;

};

int main() {

srand(1);

MonotonicStack s;

for (int i = 1; i <= 32; ++i) {

s.push(rand());

cout <(i) << endl;

}

Output

1 average cost: 1

2 average cost: 1.5

3 average cost: 1.66667

4 average cost: 1.5

5 average cost: 1.6

6 average cost: 1.5

7 average cost: 1.42857

8 average cost: 1.75

9 average cost: 1.77778

10 average cost: 1.9

11 average cost: 1.81818

12 average cost: 1.83333

13 average cost: 1.84615

14 average cost: 1.78571

15 average cost: 1.8

16 average cost: 1.8125

17 average cost: 1.82353

18 average cost: 1.77778

19 average cost: 1.78947

20 average cost: 1.75

21 average cost: 1.80952

22 average cost: 1.86364

23 average cost: 1.82609

24 average cost: 1.91667

25 average cost: 1.88

26 average cost: 1.84615

27 average cost: 1.81481

28 average cost: 1.85714

29 average cost: 1.82759

30 average cost: 1.86667

31 average cost: 1.90323

32 average cost: 1.875

[Finished in 0.5s]

Problem

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution 1: Recursion

Time complexity: O((|s| + |p|) * 2 ^ (|s| + |p|))

Space complexity: O(|s| + |p|)

C++

// Author: Huahua, 14 ms

class Solution {

public:

bool isMatch(string s, string p) {

return isMatch(s.c_str(), p.c_str());

}

private:

bool isMatch(const char* s, const char* p) {

if (*p == '\0') return *s == '\0';

// normal case, e.g. 'a.b','aaa', 'a'

if (p[1] != '*' || p[1] == '\0') {

// no char to match

if (*s == '\0') return false;

if (*s == *p || *p == '.')

return isMatch(s + 1, p + 1);

else

return false;

}

else {

int i = -1;

while (i == -1 || s[i] == p[0] || p[0] == '.') {

if (isMatch(s + i + 1, p + 2)) return true;

if (s[++i] == '\0') break;

}

return false;

}

return false;

}

};

花花酱 LeetCode 907. Sum of Subarray Minimums

By zxi on September 16, 2018

Problem

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

Idea

order matters, unlike 花花酱 LeetCode 898. Bitwise ORs of Subarrays we can not sort the numbers in this problem.
1. e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].
For A[i], assuming there are L numbers that are greater than A[i] in range A[0] ~ A[i – 1], and there are R numbers that are greater or equal than A[i] in the range of A[i+1] ~ A[n – 1]. Thus A[i] will be the min of (L + 1) * (R + 1) subsequences.
1. e.g. A = [3,1,2,4], A[1] = 1, L = 1, R = 2, there are (1 + 1) * (2 + 1) = 6 subsequences are 1 is the min number. [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4]

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 1504 ms

class Solution {

public:

int sumSubarrayMins(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

int ans = 0;

for (int i = 0; i < A.size(); ++i) {

int left = 0;

for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);

int right = 0;

for (int j = i + 1; j < A.size() && A[j] >= A[i]; ++j, ++right);

ans = (ans + static_cast<long>(A[i]) * (left + 1) * (right + 1)) % kMod;

}

return ans;

}

};

Java

// Author: Huahua, 511 ms

class Solution {

public int sumSubarrayMins(int[] A) {

final int kMod = 1000000007;

final int n = A.length;

int ans = 0;

for (int i = 0; i < n; ++i) {

int left = 0;

for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);

int right = 0;

for (int j = i + 1; j < n && A[j] >= A[i]; ++j, ++right);

ans = (int)((ans + (long)A[i] * (left + 1) * (right + 1)) % kMod);

}

return ans;

}

Python3 (TLE)

# Author: Huahua, 96/100 passed

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

ans = 0

for i in range(n):

left, right = 1, 1

while i - left >= 0 and A[i - left] > A[i]:

left += 1

while i + right < n and A[i + right] >= A[i]:

right += 1

ans += A[i] * left * right

return ans % kMod

Solution2 : Monotonic Stack

Time complexity: O(n)

Space complexity: O(n)

We can use a monotonic stack to compute left[i] and right[i] similar to 花花酱 LeetCode 901. Online Stock Span

C++

// Author: Huahua, 60 ms

class Solution {

public:

int sumSubarrayMins(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

const int n = A.size();

vector<int> left(n);

vector<int> right(n);

stack<pair<int, int>> s;

int ans = 0;

for (int i = 0; i < n; ++i) {

int len = 1;

while (!s.empty() && s.top().first > A[i]) {

len += s.top().second; s.pop();

}

s.emplace(A[i], len);

left[i] = len;

}

while (!s.empty()) s.pop();

for (int i = n - 1; i >= 0; --i) {

int len = 1;

while (!s.empty() && s.top().first >= A[i]) {

len += s.top().second; s.pop();

}

s.emplace(A[i], len);

right[i] = len;

}

for (int i = 0; i < n; ++i)

ans = (ans + static_cast<long>(left[i]) * A[i] * right[i]) % kMod;

return ans;

}

};

Java

// Author: Huahua, 154 ms

class Solution {

public int sumSubarrayMins(int[] A) {

final int kMod = 1000000007;

final int n = A.length;

Stack<Integer> nums = new Stack<>();

Stack<Integer> lens = new Stack<>();

int[] left = new int[n];

int[] right = new int[n];

int ans = 0;

for (int i = 0; i < n; ++i) {

int len = 1;

while (!nums.empty() && nums.peek() > A[i]) {

len += lens.pop(); nums.pop();

}

nums.push(A[i]);

lens.push(len);

left[i] = len;

}

nums.clear();

lens.clear();

for (int i = n - 1; i >= 0; --i) {

int len = 1;

while (!nums.empty() && nums.peek() >= A[i]) {

len += lens.pop(); nums.pop();

}

nums.push(A[i]);

lens.push(len);

right[i] = len;

}

for (int i = 0; i < n; ++i)

ans = (int)(ans + (long)A[i] * left[i] * right[i]) % kMod;

return ans;

}

Python3

# Author: Huahua, 376 ms

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

s, left, right = [], [1] * n, [1] * n

for i in range(n):

while s and s[-1][0] > A[i]:

left[i] += s.pop()[1]

s.append((A[i], left[i]))

s = []

for i in range(n - 1, -1, -1):

while s and s[-1][0] >= A[i]:

right[i] += s.pop()[1]

s.append((A[i], right[i]))

ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod

return ans

Python3 V2

# Author: Huahua, 366 ms

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

left, right = [1] * n, [1] * n

def fillLength(counts, start, end, step):

s = []

for i in range(start, end, step):

num = A[i] if step > 0 else A[i] - 1

while s and s[-1][0] > num:

counts[i] += s.pop()[1]

s.append((A[i], counts[i]))

fillLength(left, 0, n, 1)

fillLength(right, n - 1, -1, -1)

ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod

return ans

花花酱 LeetCode 905. Sort Array By Parity

By zxi on September 15, 2018

Problem

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]

Output: [2,4,3,1]

The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

Solution 1: Split Odd/Even

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> sortArrayByParity(vector<int>& A) {

vector<int> even;

vector<int> odd;

for (int a : A) {

if (a % 2) odd.push_back(a);

else even.push_back(a);

}

even.insert(end(even), begin(odd), end(odd));

return even;

}

};

Solution 2: Stable sort by key % 2

Time complexity: O(nlogn)

Space complexity: O(1) in-place

C++

// Author: Huahua, 52 ms

class Solution {

public:

vector<int> sortArrayByParity(vector<int>& A) {

stable_sort(begin(A), end(A), [](int a, int b){

return a % 2 < b % 2;

});

return A;

}

};

花花酱 LeetCode 904. Fruit Into Baskets

By zxi on September 15, 2018

Problem

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets. If you cannot, stop.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].

Example 3:

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Example 4:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

Solution: Hashtable + Sliding window

Time complexity: O(n)

Space complexity: O(1)

Keep track of the last index of each element. If a third type of fruit comes in, the new window starts after the fruit with smaller last index. Otherwise extend the current window.

[1 3 1 3 1 1] 4 1 4 … <- org window, 3 has a smaller last index than 1.

1 3 1 3 [1 1 4] 1 4 … <- new window

C++

// Author: Huahua, 144 ms

class Solution {

public:

int totalFruit(vector<int>& tree) {

map<int, int> idx; // {fruit -> last_index}

int ans = 0;

int cur = 0;

for (int i = 0; i < tree.size(); ++i) {

int f = tree[i];

if (!idx.count(f)) {

if (idx.size() == 2) {

auto it1 = begin(idx);

auto it2 = next(it1);

if (it1->second > it2->second) swap(it1, it2);

cur = i - it1->second - 1;

idx.erase(it1);

}

idx[f] = i;

ans = max(++cur, ans);

}

return ans;

}

};

花花酱 Amortized Analysis 均摊分析 SP7

Amortized Analysis

Dynamic Array

C++

Output

Monotonic Stack

C++

Output

Related Problem

花花酱 LeetCode 10. Regular Expression Matching

Problem

Solution 1: Recursion

C++

花花酱 LeetCode 907. Sum of Subarray Minimums

Problem

Idea

Solution 1: Brute Force

C++

Java

Python3 (TLE)

Solution2 : Monotonic Stack

C++

Java

Python3

Python3 V2

花花酱 LeetCode 905. Sort Array By Parity

Problem

Solution 1: Split Odd/Even

C++

Solution 2: Stable sort by key % 2

C++

花花酱 LeetCode 904. Fruit Into Baskets

Problem

Solution: Hashtable + Sliding window

C++

Huahua's Tech Road

花花酱 Amortized Analysis 均摊分析 SP7

Amortized Analysis

Dynamic Array

C++

Output

Monotonic Stack

C++

Output

Related Problem

花花酱 LeetCode 10. Regular Expression Matching

Problem

Solution 1: Recursion

C++

花花酱 LeetCode 907. Sum of Subarray Minimums

Problem

Idea

Solution 1: Brute Force

C++

Java

Python3 (TLE)

Solution2 : Monotonic Stack

C++

Java

Python3

Python3 V2

花花酱 LeetCode 905. Sort Array By Parity

Problem

Solution 1: Split Odd/Even

C++

Solution 2: Stable sort by key % 2

C++

花花酱 LeetCode 904. Fruit Into Baskets

Problem

Solution: Hashtable + Sliding window

C++