programming-examples/java/Data_Structures/AllNearestSmallerValues.java

import java.util.*;

public class AllNearestSmallerValues {

	// https://en.wikipedia.org/wiki/All_nearest_smaller_values
	public static int[] nsv(int[] a) {
		int n = a.length;
		int[] p = new int[n];
		for (int i = 0; i < n; i++) {
			int j = i - 1;
			while (j != -1 && a[j] >= a[i]) {
				j = p[j];
			}
			p[i] = j;
		}
		return p;
	}

	public static long maxInscribedRectangle(int[] heights) {
		int n = heights.length;
		int[] rheights = new int[n];
		for (int i = 0; i < n; i++) {
			rheights[i] = heights[n - 1 - i];
		}
		int[] lnsv = nsv(heights);
		int[] rnsv = nsv(rheights);
		long res = 0;
		for (int i = 0; i < n; i++) {
			int a = lnsv[i] + 1;
			int b = n - 1 - rnsv[n - 1 - i] - 1;
			long cur = (long) (b - a + 1) * heights[i];
			res = Math.max(res, cur);
		}
		return res;
	}

	public static long maxInscribedRectangle2(int[] heights) {
		long res = 0;
		Stack<Integer> spos = new Stack<>();
		Stack<Integer> sh = new Stack<>();
		sh.push(0);
		for (int i = 0; i <= heights.length; i++) {
			int h = i < heights.length ? heights[i] : 0;
			int pos = i;
			while (sh.peek() > h) {
				pos = spos.pop();
				res = Math.max(res, (long) sh.pop() * (i - pos));
			}
			spos.push(pos);
			sh.push(h);
		}
		return res;
	}

	// Usage example
	public static void main(String[] args) {
		System.out.println(maxInscribedRectangle(new int[]{1, 2, 3}));
		System.out.println(maxInscribedRectangle2(new int[]{1, 2, 3}));
		System.out.println(Arrays.toString(nsv(new int[]{1, 1, 3, 2})));
		Random rnd = new Random(1);
		for (int step = 0; step < 1000; step++) {
			int n = rnd.nextInt(10) + 1;
			int[] h = rnd.ints(n, 0, 10).toArray();
			long res1 = maxInscribedRectangle(h);
			long res2 = maxInscribedRectangle2(h);
			if (res1 != res2)
				throw new RuntimeException();
		}
	}
}