柱状图装水

11. 盛水最多的容器

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

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size()-1;
        int result = 0;

        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            result = max(result, area);
            if (height[l] < height[r]) l++;
            else r--;
        }

        return result;
    }
};

42. 接雨水

  • Given several plunks standing on an X-axis, caculate the maximum volume of water it can trap.
  • O(n) time by mono-stack.
  • O(n) time by DP. The amount of water loadable at each point is determined by leftMax and rightMax.
  • O(1) space by two pointers from two ends. leftMax and rigthMax is going-to-center mono, thus volume is mono.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left(n, 0);
        vector<int> right(n, 0);

        left[0] = height[0];
        for (int i = 1; i < n-1; i++) {
            left[i] = max(height[i-1], left[i-1]);
        }

        right[n-1] = height[n-1];
        for (int i = n-2; i > 0; i--) {
            right[i] = max(height[i+1], right[i+1]);
        }

        int result = 0;
        for (int i = 1; i < n-1; i++) {
            int real = min(left[i], right[i]);
            result += real > height[i] ? (real - height[i]) : 0;
        }

        return result;
    }
};

排序

31. 下一个排列

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

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

88. 合并两个有序数组

581. 最短无序连续子数组

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

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int begin = 0;
        int end = -1;

        int maxValue = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] >= maxValue) maxValue = nums[i];
            else end = i;
        }

        int minValue = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= minValue) minValue = nums[i];
            else begin = i;
        }

        return end-begin+1;
    }
};

Two pointers sometimes is an implementation of mono-stack or mono-queue. Mono here means that, under the problem’s condition, the optimal value of left pointer is a mono function of right pointer, and vice versa. One needs to find out the mover changing condition, this is typically when moving more won’t make things better.

题解

  • 3 Longest Substring Without Repeating Characters
    • O(n) time and O(1) space. Mono function is increasing. When there is repeat, moving is bad.
  • 15 3Sum
    • O(n^2) time. Sort then use two pointers.
  • 16 3Sum Closest
    • 3Sum but return the triplet whose sum is closest to a target.
    • O(n^2) time. Sort and two pointers.
  • 26 Remove Duplicates from Sorted Array
  • 27 Remove Element
  • 30 Substring with Concatenation of All Words
    • Given a string and a word (all same length) list, find all substrings that are made up of the whole word list.
    • O(nm) time and O(m) space, where n is length of string and m is length of word. Word-level two pointer, start from 0 - m-1.
    • DP is also possible. For each index, save the longest valid substring ended with it, and corresponding word usages.
  • 75 Sort Colors
    • Sort sequences consisting of 1, 2, 3.
    • O(n) time and one pass by two pointers. Not related to mono things.
  • 76 Minimum Window Substring
    • Given S and T, find minimum window in S containing AT LEAST all letters in T.
    • O(n) time by two pointers.
  • 80 Remove Duplicates from Sorted Array II
    • Given a sorted array, remove redundant elements such that no element appears more than 2 times.
    • O(n) time by two pointers. Not related to mono things.
  • 159 Longest Substring with At Most Two Distinct Characters
    • Easy O(n) time two pointers.
  • 209 Minimum Size Subarray Sum
    • O(n) time by two pointers.
    • O(nlog(n)) time by binary search the minimum size.
  • 259 3Sum Smaller
    • O(n^2) time by sorting first. Similar to 3Sum Closest.
  • 287 Find the Duplicate Number
    • O(n) time and O(1) space by Floyd Cycle Detection Algorithm. No mono things.
  • 340 Longest Substring with At Most K Distinct Characters
    • O(n) time and O(1) space, typical sliding window.
  • 424 Longest Repeating Character Replacement
    • Given a string, one can at most alter k characters. Find the maximum length of repeat character string.
    • O(n) time. Note that these k characters must be in a sliding window.
    • Use per-character queue also works.
    • O(26) space, maintaining maximum character count ever encountered in the sliding window. The length of sliding window is mono increasing.
  • 457 Circular Array Loop
    • Find circles in integer array. Floyd Cycle Detection Algorithm.
    • Pitfall: only mark elements as zero when the case is confirmed invalid.
  • 481 Magical String
    • Build recursive string: 1221121… -> 1 22 11 2 1 -> 12211…
    • Generate string according to its prefix.
  • 611 Valid Triangle Number
    • Sort and use two pointers to find solve “two sum > nums[largestIdx]”
  • 713 Subarray Product Less Than K
  • 828 Unique Letter String
    • Define UNIQ(s) is the number of unique letters in a string. Find sum of UNIQ of all substrings of S.
    • At each step, calculate UNIQ of substrings ending by that character. Maintain a character index map.
  • 904 Fruit Into Baskets
    • Find longest subarray with at most 2 distinct numbers.
  • 986 Interval List Intersections
    • Given two non-intersect interval lists, calculate their intersected result.
    • Merge sort. Always throw the interval with lower end and keep the rest interval.
  • 992 Subarrays with K Different Integers
    • Prefix-sum-like method, Find number of subarrays with AT MOST K different integers.
  • 1004 Max Consecutive Ones III
    • Given a 0-1 array, one can change 0 to 1 at most K times. Find maximum consecutive ones.
  • 1031 Maximum Sum of Two Non-Overlapping Subarrays
    • Given a number array, find maximum of two non-overlapping M-length and L-length subarray.
    • Maintain last M and L length sum and maximum sum of M and L length arrays.

参考资料