962. Maximum Width Ramp

Medium

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn't exist, return 0.

Example 1:

Input: [6,0,8,2,1,5]
Output: 4
Explanation:
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation:
The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

题目大意：在一个数组中，找到两个相距最远的顺序对。

解题思路：利用栈保存起始数，从而搜索结束数。

下面利用Go尝试解题，

func maxWidthRamp(nums []int) (ans int) {
    var stack []int
    top := func(s []int) int {
        if len(s) == 0 {
            panic("access out of boundary")
        }
        return s[len(s)-1]
    }
    pop := func(s []int) []int {
        if len(s) == 0 {
            panic("access out of boundary")
        }
        return s[:len(s)-1]
    }
    push := func(s []int, n int) []int {
        return append(s, n)
    }

    //push the start candiator
    for i, n := range nums {
        if len(stack) == 0 || n < nums[top(stack)] {
            //if current 'n' is greater than stack top
            //  it is impossible to be a candiator
            stack = push(stack, i)
        }
    }

    for i := len(nums) - 1; i >= 0; i-- {
        //find the end candiator for each of the stack top
        for len(stack) > 0 && nums[i] >= nums[top(stack)] {
            ans = Max(ans, i-top(stack))
            stack = pop(stack)
        }
    }
    return
}

在Leetcode上测试代码

Success
[Details]
Runtime: 48 ms, faster than 57.58% of Go online submissions for Maximum Width Ramp.
Memory Usage: 7 MB, less than 100.00% of Go online submissions for Maximum Width Ramp.

668. Kth Smallest Number in Multiplication Table

Hard

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output:
Explanation:
The Multiplication Table:
1 2 3
2 4 6
3 6 9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output:
Explanation:
The Multiplication Table:
1 2 3
2 4 6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

1. The m and n will be in the range [1, 30000].
2. The k will be in the range [1, m * n]

题目大意：在乘法表中寻找第k个最小的数。

解题思路：乘法表中的数按一定规律递增。用二分搜索，每次检测mid是否有k个小的数。

下面用Go来尝试解题，

func findKthNumber(row, col, target int) int {
    LEX := func(x int) (cnt int) {
        for i := 1; i <= row; i++ {
            if x/i > col {
                cnt += col //count the whole row
            } else {
                cnt += x / i //count the ele before x, first several cols
            }
        }
        return
    }

    low, high := 1, row*col+1
    for low < high {
        mid := low + (high-low)/2
        cnt := LEX(mid)

        if cnt >= target {
            high = mid
        } else {
            low = mid + 1
        }
    }

    return low
}

在Leetcode上测试代码

Success
[Details]
Runtime: 44 ms, faster than 35.29% of Go online submissions for Kth Smallest Number in Multiplication Table.
Memory Usage: 2 MB, less than 100.00% of Go online submissions for Kth Smallest Number in Multiplication Table.