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:
- The
mandnwill be in the range [1, 30000]. - The
kwill 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.
