算法编程题-区间最小数乘区间和的最大值，基于数组中的数字拼接可得的小于目标值的最大数

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

原题描述

给定一个数组，定义一个子数组的值为：该子数组中的最小值乘以该子数组的和，现在需要找到值最大的子数组。比如，对于数组[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. 从前往后用单调栈找出左边最近的比当前元素要小的元素的位置+1
	leftSmaller := 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. 从后往前遍历用单调栈找到右边最近的比当前元素要小的位置-1
	rightSmaller := 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 := 0
	for 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 = 0
			for 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 = num
			return
		} 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 := 11
	for num > 0 {
		numbers[k] = num % 10
		k--
		num /= 10
	}
	return numbers[k + 1:]
}

// getMaxSmaller 返回有序数组nums中小于等于target的最大整数
func getMaxSmaller(nums []int, target int) int {
	low := 0
	high := len(nums) - 1
	for low < high {
		mid := (low + high + 1) / 2
		if 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)$

参考

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