这里分享两道字节面试常考但是不是leetcode原题的两道题目。

区间最小数乘区间和的最大值

原题描述

给定一个数组，定义一个子数组的值为：该子数组中的最小值乘以该子数组的和，现在需要找到值最大的子数组。比如，对于数组[6, 2, 1]，应当输出36。

思路简述

该题虽然不是leetcode原题，但是和经典题接雨水的思路是一样的。先从暴力思路入手，最暴力最直观的思路就是遍历每一个子数组，然后在遍历这个子数组得出子数组的最小值和和，这种做法的时间复杂度达到了$O(n^3)$。先尝试在这一个基础上进行优化，减少遍历次数。可以优化遍历方式，在遍历的同时计算当前子数组的最小值和和，这样时间复杂度就减少到了$O(n^2)$。但是这样的时间复杂度是肯定不够的，还需要优化。
考虑枚举，换一个角度想，能不能枚举没有的最小值，也就是我们遍历数组，以当前位置作为最小值，那么当前位置的数能够作为什么样的子数组的最小值呢，显然是子数组中不会存在小于该数的数，那么就可以从当前位置往左看，第一个小于当前数的位置，以及往右看，第一个小于当前数的位置，以上两个位置夹的子数组就是以当前数为最小数的情况下，对应的最优的子数组，因为在最小数确定的情况下，子数组自然是越长越好。可是怎么去找到以上的两个位置呢？可以基于单调栈以$O(n)$的时间复杂度预处理得到所有位置的左边第一个小于的数，右边第一个小于的数，这样整体的时间复杂度就减少到了$O(n)$。
以寻找左边最近的较小的数字的过程为例来说明单调栈的过程，首先是从左往右遍历数组，维护一个单调递增栈，为什么是递增，如下图，假设此时维护的栈不满足严格的递增，遍历到一个新的数11，其左边的第一个较小的数字是8，而10永远没有机会，因为一个数字如果比10大，也一定会大于8，而我们要找的左边最近的，相当与10会被8覆盖掉，所以我们要维护成一个单调递增栈。具体的思路就是在遍历的过程中，先把栈顶大于等于当前数字的数pop出去，然后根据栈中的情况决定左边最近的较小的数字的位置是什么，然后将当前数字也加入到栈中，这样维护的栈就是一个单调递增栈。

代码实现

func MaxVInterval(arr []int) int {n := len(arr)// 1. 从前往后用单调栈找出左边最近的比当前元素要小的元素的位置+1leftSmaller := make([]int, n)stack := gulc.NewStack[int]()for i := 0; i < n; i++ {for !stack.IsEmpty() && arr[stack.Top()] >= arr[i] {stack.Pop()}if stack.IsEmpty() {leftSmaller[i] = 0} else {leftSmaller[i] = stack.Top() + 1}stack.Push(i)}// 2. 从后往前遍历用单调栈找到右边最近的比当前元素要小的位置-1rightSmaller := make([]int, n)stack.Clear()for i := n - 1; i >= 0; i-- {for !stack.IsEmpty() && arr[stack.Top()] >= arr[i] {stack.Pop()}if stack.IsEmpty() {rightSmaller[i] = n - 1} else {rightSmaller[i] = stack.Top() - 1}stack.Push(i)}// 3. 利用前缀和 预处理区间和prefixSum := make([]int, n + 1)sum := 0for i := 0; i < n; i++ {sum += arr[i]prefixSum[i + 1] = sum}// 4. 推导答案ans := arr[0] * (prefixSum[rightSmaller[0] + 1] - prefixSum[leftSmaller[0]])for i := 1; i < n; i++ {ans = max(ans, arr[i] * (prefixSum[rightSmaller[i] + 1] - prefixSum[leftSmaller[i]]))}return ans
}

复杂度分析

• 时间复杂度：$O(n)$，预处理过程，代码实现看起来有两层循环，但是两层循环里的操作只有栈的push和pop，而考虑到数组中的每一个元素最多进栈一次，出栈一次，所以实际上的循环次数是$O(n)$级别的
• 空间复杂度：$O(n)$

基于数组中的数字拼接可得的小于目标值的最大数

原题描述

给定一个数组，数组里的数字只包括0-9的数字，给定一个目标值target，要求出用数组里面的数字组装成最大的小于target的数字。比如，对于数组[5, 4, 9, 2]和目标值16345,应当输出9999

思路简述

这题比较容易想到解法，但难在任何优雅简洁地实现。笔者的思路就是根据目标值来逐位构造，从目标值的最高位开始，在数组里找到最大的小于等于最高位的数字，如果找到的是一个小的数，那么剩余的位数可以全部采用数组中的最大数，因为已经保证了一定比目标值要小，如果找到的是相等，那么需要在下一位找类似的分析，如果没找到，则需要回退到前一位，前一位一定是在数组中出现的，此时可以尝试去数组中比该数稍小的一个数，如果能取到，剩余数字全部去最大数即可，如果没找到，需要再回退到上一位。回退的终点是不在数组中了，此时可以取目标值位数-1的位数，每一位用最大值填充。如果目标值所有位的数字都出现在数组中，则也需要往前回退。回退需要使用回溯来实现，实现代码比较复杂。

代码实现

func MaxNumber(nums []int, target int) int {sort.Slice(nums, func(i, j int) bool {return nums[i] < nums[j]})ans := -1// 从最高位开始numbers := getNumbers(target)n := len(numbers)var dfs func(i, num int, flag bool) dfs = func(i, num int, flag bool) {if ans != -1 {return}if i == -1 {   // 回退的终点ans = 0for j := 0; j < n - 1; j++ {ans = ans * 10 + nums[len(nums) - 1]}return}pos := getMaxSmaller(nums, numbers[i])  if pos == -1 {   // 需要回退dfs(i - 1, num / 10, true)}if flag {   // 发生了回退if pos == 0 {dfs(i - 1, num / 10, true)} else {pos--}}if ans != -1 {return}num = num * 10 + nums[pos]i++if nums[pos] < numbers[i - 1] {   // 这个保证了一定小于，所以后续数字全部取最大数字即可for i < n {num = num * 10 + nums[len(nums) - 1]i++}ans = numreturn} else if i == n {   // 特殊情况，说明target的每一位都出现在了数组中, 需要回退dfs(i - 1, num / 10, true)}dfs(i, num, flag)}dfs(0, 0, false)return ans
}// getNumbers 返回num的各位数字
func getNumbers(num int) []int {if num == 0 {return []int{0}}numbers := make([]int, 12)k := 11for num > 0 {numbers[k] = num % 10k--num /= 10}return numbers[k + 1:]
}// getMaxSmaller 返回有序数组nums中小于等于target的最大整数
func getMaxSmaller(nums []int, target int) int {low := 0high := len(nums) - 1for low < high {mid := (low + high + 1) / 2if nums[mid] > target {high = mid - 1} else {low = mid}}if nums[low] > target {return -1}return low
}

复杂度分析

• 时间复杂度：$O(1)$，可以认为是常量级别，因为数组是由0-9的数字组成的，长度一般不超过10，然后逐位构造，考虑到整数最多也只有64位，也是有限的
• 空间复杂度：$O(1)$

参考

• 求区间最小数乘区间和的最大值